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

问题描述：

试图制作一个只检查的程序，如果string s1 的排列存在于string s2与否.

Trying to make an program where it just check, if permutation of string s1 exists in string s2 or not.

在程序下方创建，适用于以下测试用例.

Created below program and it works for below test case.

输入:

s1 = "ab"
s2 = "eidballl"

输出:

真

说明:s2 包含 s1 的一个排列(即 ba).

Explanation: s2 contains one permutation of s1 (that is ba).

但是这会失败，输入 s2="sdfdadddbd" , s1="ab", expected as, false，但得到 true.

But this get fail when, input s2="sdfdadddbd" , s1="ab", expected as, false, but got true.

我想弄清楚这里缺少什么.使用滑动窗口方法.在 c# 中我的代码下面:

I'm trying to figure out what is missing here. Using a sliding window approach. Below my code in 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.这些是简单、高效、低复杂性的公认解决方案:

I guess the question is similar to LeetCode 567. These are simple, efficient, low-complexity accepted solutions:

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;
    }
}

Java

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;
    }
}

Python

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

参考

代码在以下链接中解释:

Reference

The codes are explained in the following links:

LeetCode 567 解决方案

LeetCode 567讨论区

这两个答案也很有用:

链接 1
链接 2

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

Java

Python

参考

Reference

相关推荐