我想做一个程序，在这个程序中，它只需要检查 string s1 存在于 string s2 或不。
创建了下面的程序，它可以用于下面的测试案例。
输入：输入
s1 = "ab"
s2 = "eidballl"
输出：
True
解释: s2 包含一个排列组合 s1 (即 ba).
但当输入 s2="sdfdadddbd" , s1="ab", 预期 作为： false但 得到 true.
我想弄清楚这里缺少什么。采用滑动窗口的方式。下面是我的代码，在 c#:
public bool CheckInclusion(string s1, string s2) {
var intCharArray = new int[256];
foreach(char c in s1)
{
intCharArray[c]++;
}
int start=0,end=0;
int count=s1.Length;
bool found=false;
while(end<s2.Length)
{
if (intCharArray[s2[end]]>0) { count--;}
intCharArray[s2[end]]--;
Console.WriteLine("end:" + end + " start:"+ start);
if(end-start==s1.Length) {
if (count==0) {return true;}
if (intCharArray[s2[start]]>=0)
{
count++;
}
intCharArray[s2[start]]++;
start++;
}
end++;
}
return false;
}
我想这个问题类似于 LeetCode 567. 这些都是简单、高效、低复杂度的公认解决方案。
C#
class Solution {
public bool CheckInclusion(string s1, string s2) {
int lengthS1 = s1.Length;
int lengthS2 = s2.Length;
if (lengthS1 > lengthS2)
return false;
int[] countmap = new int[26];
for (int i = 0; i < lengthS1; i++)
countmap[s1[i] - 97]++;
int[] bCount = new int[26];
for (int i = 0; i < lengthS2; i++) {
bCount[s2[i] - 97]++;
if (i >= (lengthS1 - 1)) {
if (allZero(countmap, bCount))
return true;
bCount[s2[i - (lengthS1 - 1)] - 97]--;
}
}
return false;
}
private bool allZero(int[] s1, int[] s2) {
for (int i = 0; i < 26; i++) {
if (s1[i] != s2[i])
return false;
}
return true;
}
}
class Solution {
public boolean checkInclusion(String s1, String s2) {
int lengthS1 = s1.length();
int lengthS2 = s2.length();
if (lengthS1 > lengthS2)
return false;
int[] countmap = new int[26];
for (int i = 0; i < lengthS1; i++) {
countmap[s1.charAt(i) - 97]++;
countmap[s2.charAt(i) - 97]--;
}
if (allZero(countmap))
return true;
for (int i = lengthS1; i < lengthS2; i++) {
countmap[s2.charAt(i) - 97]--;
countmap[s2.charAt(i - lengthS1) - 97]++;
if (allZero(countmap))
return true;
}
return false;
}
private boolean allZero(int[] count) {
for (int i = 0; i < 26; i++)
if (count[i] != 0)
return false;
return true;
}
}
class Solution:
def checkInclusion(self, s1, s2):
count_map_s1 = collections.Counter(s1)
count_map_s2 = collections.Counter(s2[:len(s1)])
for i in range(len(s1), len(s2)):
if count_map_s1 == count_map_s2:
return True
count_map_s2[s2[i]] += 1
count_map_s2[s2[i - len(s1)]] -= 1
if count_map_s2[s2[i - len(s1)]] == 0:
del(count_map_s2[s2[i - len(s1)]])
return count_map_s2 == count_map_a
代码的解释在下面的链接中。
这两个答案也是很有用的，可以参考一下。
你需要检查所有的换元字符存在于字符串的任何范围[i, i + p.Length)中。
static class StringExtensions
{
public static bool ContainsAnyPermutationOf(this string str, string p)
{
Dictionary<char, int> chars_count = p.CreateChar_CountDictionary();
for (int i = 0; i <= str.Length - p.Length; i++)
{
string subString = str.Substring(i, p.Length);
if (DictionaryMatch(chars_count, subString.CreateChar_CountDictionary()))
{
return true;
}
}
return false;
}
private static bool DictionaryMatch(Dictionary<char, int> dictionary1, Dictionary<char, int> dictionary2)
{
if (dictionary1.Count != dictionary2.Count)
{
return false;
}
foreach (var kvp in dictionary1)
{
if (!dictionary2.ContainsKey(kvp.Key))
{
return false;
}
dictionary2[kvp.Key] = dictionary2[kvp.Key] - 1;
if (dictionary2[kvp.Key] == 0)
{
dictionary2.Remove(kvp.Key);
}
}
return true;
}
private static Dictionary<char, int> CreateChar_CountDictionary(this string str)
{
Dictionary<char, int> dic = new Dictionary<char, int>();
for (int i = 0; i < str.Length; i++)
{
if (!dic.ContainsKey(str[i]))
{
dic.Add(str[i], default);
}
dic[str[i]] = dic[str[i]] + 1;
}
return dic;
}
}
使用。
static void Main(string[] args)
{
Console.WriteLine("sdfdadddbd".ContainsAnyPermutationOf("ab"));
}
确切地复制和粘贴你的代码，我得到了。False 对于以下输入（虽然你提到了 true) :
string s1 = "ab";
string s2 = "eidballl";
在按照算法的时候，我得到了这些。
1.在你的这部分代码之后
var intCharArray = new int[256];
foreach (char c in s1)
{
intCharArray[c]++;
}
当我运行时，我得到了这样的结果 Console.WriteLine(string.Join(",", intCharArray));:
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
如你所见，索引97和98的元素为1，其他元素为0。
2.你有这个（在while循环中）。
if (intCharArray[end] > 0) { count--; }
我有个问题，当 intCharArray[end] > 0 是 true?
有了我们从数字1中知道的东西，所有元素的 intCharArray 除了指数为97和98的两个元素外，其他元素的最大值为0。end 可以 s2.Length.长度 s2 必然是97和98 intCharArray[end] > 0 成为 true. 所以... count--; 对大多数人来说是不可及的 s2's.
3.你声明 count 自此 count--; 的值没有变化。count 和 count == 0是 false 当 s1 不是 "" (s1.Length 不是0）。)
再来 ... 是无法到达的。
if (count == 0)
{
...
}
4.所以在while循环中唯一可以到达的行是。
intCharArray[end]--;
end++;
while循环是没有用的，因为它只是增加了 end 和减少 intCharArray[end] 每次都是如此。
5.最后返回 false 因为
if (end - start == s1.Length) { return true; }
是无法到达的。
总之我有另一个解决方案，用 推拉窗算法 您在上面提到的，如下。
private static bool ContainsAnyPermutationOf(this string string2, string string1)
{
for (int i = 0; i <= string2.Length - string1.Length; i++)
{
bool thereIsAViolation = false;
string string1LengthSubStringOfString2 = "";
for (int j = i; j < i + string1.Length; j++)
{
string1LengthSubStringOfString2 += string2[j];
}
for (int j = 0; j < string1.Length; j++)
{
if (!string1LengthSubStringOfString2.Contains(string1[j]))
thereIsAViolation = true;
}
if (!thereIsAViolation)
return true;
}
return false;
}
1.生成 a 的子串 string2 长短 string1.
2.检查子串是否包含string1的所有字符。如果是 return true如果没有，则转到数字1，并按照这个路径直到所有带有所述属性的子字符串都被选中，然后 return false.
感谢 @M.Khooryani 提出的一个 bug。
static void Main()
{
string s1 = "fe";
string s2 = "abcdefgh";
Console.WriteLine(s2.ContainsAnyPermutationOf(s1));
}
你需要静态类来使用上面的解决方案。
虽然我已经测试过了，但请告诉我是否有帮助（只是一个反馈）。
还有
StackOverflow是一个关于实际代码的具体问题的问答网站。"我写了一些错误的代码，我无法修复 "这不是一个问题，而是一个故事，甚至不是一个有趣的故事。"为什么从0中减去1会产生一个比0大的数字，导致我在第12行与0的比较错误地变成了真？"这是一个关于实际代码的具体问题。
来自 Eric Lippert的网站.