力扣567.字符串的排列

题目

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例2:

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

注意：

输入的字符串只包含小写字母

两个字符串的长度都在 [1, 10,000] 之间

解题

2月还真就是滑动窗口月，不少滑动窗口也可以用双指针做。

理解起来不难，就是用字符串1中的字母组成字符串2中的子串。比如字符串1"abc",那么字符串2中包含有abc随机组成的字串都是可以的比如，abc，acb，bac，bca，cab，cba这些都是可以算作组成。只要字符串2中包含有这6中组成中的一种即可返回true。
先对于字母数进行统计赋值
对于这种我们可以选取一个边界固定另外一个边界滑动的方式来解决。
左边界固定就是left=0；随后对于右边界right进行往后的遍历，遍历要求是对于之前对字符串1计算统计的字母个数进行一个抵消算法，在初次对字符串1的遍历之中我们已经统计过了字符串1的各个字母的个数，在对字符串2的right的右移过程之中对于字符统计要做一个抵消就是基于已有的统计的负值上检测到的数字进行加运算。当达到恰好成都一致且字母数达到平衡那么就是符合条件。

bool checkInclusion(char* s1, char* s2) {

   int n = strlen(s1), m = strlen(s2);//n,m分别对应1，2的长度

   if (n > m) {//如果字符串1大于字符串2的长度直接返回false

       return false;

   }

   int cnt[26];//建立小写字母数组

   memset(cnt, 0, sizeof(cnt));//为每个字母对应的数组空位置0

   for (int i = 0; i < n; ++i) {

       --cnt[s1[i] - 'a'];//将字符串1内的字符进行统计（按负数统计）

   }

   int left = 0;

   for (int right = 0; right < m; ++right) {

       int x = s2[right] - 'a';//获取right对应字母在cnt中的位置

       ++cnt[x];//计数加一

       while (cnt[x] > 0) {            //当所计数的字母数在字符串2内的数目大于字符串1内的数目

           --cnt[s2[left] - 'a'];      //left对应字母在cnt中计数减1

           ++left;                     //left右移

       }

       if (right - left + 1 == n) {    //若左右指针间长度等于s1的长度

           return true;                //返回true

       }

   }

   return false;

}

巴特西

力扣567.字符串的排列—C语言实现

题目

解题

最新文章

热门文章