|
先给题
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
来源：力扣（LeetCode）
链接：https:///problems/permutation-in-string
今天第一次，没有看题解做出来了，时间和内存还都可以的情况下。继续加油！
1.暴力破解
以后就不谈暴力破解了，一般这样的题暴力破解都超时
2.自己想的
说一说自己的想法
（1）总体思想
第一眼看到这个字符串匹配的问题，就想到了滑动窗口（双指针），最近做这样的题蛮多的。
（看了题解才知道我用的是双指针，双指针和滑动窗口并不是一摸一样的，具体区别可以看https://blog.csdn.net/WizardWXY/article/details/113703470，感觉讲的蛮好的）
我们先来理解一下题，题的意思是我们要判断s2中是否存在一个与s1等长度的子数组，元素种类与元素个数与s1完全相同。有就返回1，没有就返回0.
（一开始我是按照顺序也一致做的，不管正序或者逆序。但后来发现理解错题了。）
所以，我们要想办法来记录一下子字符串的的元素状况，我们开辟一个长度为26的数组来记录个元素的数量。这个数组来记录s1字符串元素的情况。当右指针移动时，判断这个元素个数是否为0，不为0代表目前子字符串的元素种类和个数都没问题，如果为0，就表明这个元素要么不存在，要么前面存在这个元素的数量已经超过了s1中的，这时候我们就要左指针移动，并且要再把左边移动出来的元素再记录进去。
那么记下来的问题就是如何判断查找出符合的情况以及左指针根据什么条件移动。（这也是最难的两个点）
（2）我们先来谈一谈左指针如何移动。
左指针一旦移动，就代表了当前子字符串的元素种类或者数目不符合要求，左指针需要移动，那么左指针移动到什么地步，子字符串就符合了？
极限的情况，我们遇到了一个s1根本不存在的元素，那么此时子字符串肯定不符合要求了，让left和right移动到这个元素的后面重新开始。
而如果我们遇到的元素是前面出现的元素，只是数量达不到要求，那么左指针只要移动到与该元素相同的那个元素的后面，我们就可以不用再移动了，此时子字符串肯定符合要求。
根据上面的两种情况，我们可以得出，只要右指针指向的元素的可用值为0，我们左指针就要一直移动，直到左指针达到右指针的位置。当左指针不再移动时，再来判断右指针指向元素是否大于0（因为右指针指向的元素不存在，那么左指针就移动到右指针的位置，所以还需要在判断一下数值），大于0，就说明这个元素是存在于s1的，记录影响值，=0，就说明这个元素不存在，左指针继续移动一位，跳过这个元素。
（3）再来谈一下判断有无的条件
一开始我是这么想的，当这个记录数值的26位数组所有值都为0的时候，就代表着元素全部用完了，但这样太费时了。
所以我们来找另一种判断的方法。
假设一开始我们就没遇到不符合的元素，那么右指针一直移动，当这个子数组元素情况与s1相等时，此时我们就可以判断它是符合条件的。这样的话如果我们遇到不符合的元素，那么此时右指针减去左指针+1 一定是小于等于s1的长度的。
根据上述假设，我们就可以知道，当判断后如果右指针减去左指针+1（即当前子数组长度）达到了s1的长度，那么我们就可以说存在符合题意的子数组了。
（4）理解完了就上代码
 
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int left = 0, right = 0;
vector<int> v(26, 0);
for (int i = 0; i < s1.length(); i++)
v[(int)s1[i] - 97]++;
while (right < s2.length()) {
if (v[(int)s2[right] - 97] > 0)
v[(int)s2[right] - 97]--;
else
{
while (v[(int)s2[right] - 97] == 0 && left < right) {
v[(int)s2[left] - 97]++;
left++;
}
if (v[(int)s2[right] - 97] > 0)
v[(int)s2[right] - 97]--;
else
left++;
}
right++;
if (right - left == s1.length())
return 1;
}
return 0;
}
};
View Code3.题解
题解有两种，一种是滑动窗口，一种是双指针（和我想的一摸一样），所以在这里我们就来说滑动窗口。
其实思路差不很多，我们依然是开辟数组来记录元素的状况。只不过这次我们是来记录两个子数组的情况。
要想符合题意，s2的子数组长度肯定是s1的长度，所以只要两个数组的元素情况相同，我们就可以返回1。左指针跟着右指针移动，窗口的长度固定不变。
官方题解还对这个方法进行了优化，我们可以只开辟一个数组来记录情况，这个数组用来记录上述方法中用来记录元素状况的两个数组的差，判断条件我们可以用一个diff来记录他们的不同值，当差不为0，就让diff++，只要diff不为0，那么就不符合。
这是未优化的
1 class Solution {
2 public:
3 bool checkInclusion(string s1, string s2) {
4 int n = s1.length(), m = s2.length();
5 if (n > m) {
6 return false;
7 }
8 vector<int> cnt1(26), cnt2(26);
9 for (int i = 0; i < n; ++i) {
10 ++cnt1[s1[i] - 'a'];
11 ++cnt2[s2[i] - 'a'];
12 }
13 if (cnt1 == cnt2) {
14 return true;
15 }
16 for (int i = n; i < m; ++i) {
17 ++cnt2[s2[i] - 'a'];
18 --cnt2[s2[i - n] - 'a'];
19 if (cnt1 == cnt2) {
20 return true;
21 }
22 }
23 return false;
24 }
25 };
View Code
这是优化的
1 class Solution {
2 public:
3 bool checkInclusion(string s1, string s2) {
4 int n = s1.length(), m = s2.length();
5 if (n > m) {
6 return false;
7 }
8 vector<int> cnt(26);
9 for (int i = 0; i < n; ++i) {
10 --cnt[s1[i] - 'a'];
11 ++cnt[s2[i] - 'a'];
12 }
13 int diff = 0;
14 for (int c: cnt) {
15 if (c != 0) {
16 ++diff;
17 }
18 }
19 if (diff == 0) {
20 return true;
21 }
22 for (int i = n; i < m; ++i) {
23 int x = s2[i] - 'a', y = s2[i - n] - 'a';
24 if (x == y) {
25 continue;
26 }
27 if (cnt[x] == 0) {
28 ++diff;
29 }
30 ++cnt[x];
31 if (cnt[x] == 0) {
32 --diff;
33 }
34 if (cnt[y] == 0) {
35 ++diff;
36 }
37 --cnt[y];
38 if (cnt[y] == 0) {
39 --diff;
40 }
41 if (diff == 0) {
42 return true;
43 }
44 }
45 return false;
46 }
47 };
View Code
想详细了解的可以去这里https:///problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/
|
