c# - 查找一个字符串到另一字符串程序的排列

Question

尝试编写一个程序，仅检查string s1的排列是否存在于string s2中或不。

创建了以下程序，它适用于以下测试用例。

输入:

s1 = "ab"
s2 = "eidballl"

输出:

正确

说明:s2 包含 s1 的一种排列(即 ba)。

但是当输入 s2="sdfdadddbd" 、 s1="ab"、expected as、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;
        }

Answer 1

需要检查字符串的任意[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"));
    }