題目鏈接
tag:
- Medium整慎；
- Sliding Window;
question
??Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.
Example 1:
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input:s1= "ab" s2 = "eidboaoo"
Output: False
Note:
- The input strings only contain lower case letters.
- The length of both given strings is in range [1, 10,000].
思路：
??本題給了兩個(gè)字符串s1和s2淋淀，問(wèn)我們s1的全排列的字符串任意一個(gè)是否為s2的字串赦颇。雖然題目中有全排列的關(guān)鍵字脯倚，但是跟之前的全排列的題目的解法并不一樣纲酗，如果遍歷s1所有全排列的情況脚猾，然后檢測(cè)其是否為s2的子串，非常不高效的，最大10000的階乘饰及，估計(jì)會(huì)超時(shí)蔗坯。
??正確做法應(yīng)該是使用滑動(dòng)窗口 Sliding Window 的思想來(lái)做，可以使用兩個(gè)哈希表來(lái)做燎含，先分別統(tǒng)計(jì)s1和s2中前n1個(gè)字符串中各個(gè)字符出現(xiàn)的次數(shù)宾濒，其中n1為字符串s1的長(zhǎng)度，這樣如果二者字符出現(xiàn)次數(shù)的情況完全相同屏箍，說(shuō)明s1和s2中前n1的字符互為全排列關(guān)系绘梦，那么符合題意了，直接返回true赴魁。如果不是的話卸奉，那么我們遍歷s2之后的字符，對(duì)于遍歷到的字符颖御，對(duì)應(yīng)的次數(shù)加1榄棵，由于窗口的大小限定為了n1，所以每在窗口右側(cè)加一個(gè)新字符的同時(shí)就要在窗口左側(cè)去掉一個(gè)字符潘拱，每次都比較一下兩個(gè)哈希表的情況疹鳄，如果相等，說(shuō)明存在芦岂，代碼如下：
class Solution {
public:
bool checkInclusion(string s1, string s2) {
// 一定要做特殊處理
if (s1.size() > s2.size())
return false;
if (s1.size() == 0)
return true;
if (s2.size()==0)
return false;
int n1 = s1.size(), n2 = s2.size();
// 雙哈希
vector<int> m1(128), m2(128);
for (int i = 0; i < n1; ++i) {
++m1[s1[i]];
++m2[s2[i]];
}
if (m1 == m2)
return true;
for (int i = n1; i < n2; ++i) {
++m2[s2[i]];
--m2[s2[i - n1]];
if (m1 == m2)
return true;
}
return false;
}
};
