LeetCode 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"

输出: True

解释: s2 包含 s1 的排列之一 ("ba").

示例2:

输入: s1= "ab" s2 = "eidboaoo"

输出: False
解法：开始想跑dfs 跑全排列，然后用KMP 去匹配，但是后来想了一下，不用那么复杂，因为全是小写字母，所以只需要s2 和s1 这段字符串的字符数量一样就可以了，
因为s1 的子串可以重新组合，必然能和s2 匹配成功。

class Solution {

public:

    bool check(int a[])

    {

        for(int i=;i<;i++)

        {

            if(a[i]!=)

                return false;

        }

        return true;

    }

    bool checkInclusion(string s1, string s2) {

        int len1=s1.length();int len2=s2.length();

        if(len1>len2 || len1== || len2==)

        {

            return false;

        }

        else

        {

            int a[]={};

            for(int i=;i<len1;i++)

            {

                a[s1[i]-'a']--;

                a[s2[i]-'a']++;

            }

            for(int j=len1;j<len2;j++)

            {

                if(check(a))

                {

                    return true;

                }

                a[s2[j-len1]-'a']--;

                a[s2[j]-'a']++;

            }

            return check(a);

        }

    }

};

巴特西

LeetCode 字符串的排列

最新文章

热门文章