今天是滑动窗口了，终于不是双指针了，感觉双指针的题还没做够😂。
两道中等题。
3. Longest Substring Without Repeating Characters
Analysis
寻找无重复字符的最长子串，这个问题好像可以用 KMP 来解决，但是我早就忘记了 KMP 怎么用了。然而，遗憾的是滑动窗口的题我也没做过，所以就只能暴力解决了。没想到，竟然还可以过。
Code
method 1
比较尴尬的是，一开始老是想用滑动窗口来做，结果提交了 3 次没过，直接删了重新写暴力解法，一次就过了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/* method 1: violent solutions */
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length(), i, j, ret = 0;
for(i = 0; i < len; i++) {
string tmp;
tmp += s[i];
for(j = i + 1; j < len; j++) {
if(tmp.find(s[j]) == string::npos) tmp += s[j];
else break;
}
if(tmp.length() > ret) ret = tmp.length();
}
return ret;
}
};
method 2
学习一下滑动窗口的解法。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/* method 2: use a set simulate hashtable to judge whether the char has appeared or not. */
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> ht;
int n = s.length();
int rk = -1, ans = 0;
for(int i = 0; i < n; i++) {
if(i != 0) {
ht.erase(s[i - 1]);
}
while(rk + 1 < n && ht.find(s[rk + 1]) == ht.end()) {
ht.insert(s[rk + 1]);
rk++;
}
ans = max(ans, rk - i + 1);
}
return ans;
}
};
滑动窗口好像必须要有一个 hash 表来判断是否出现重复的字符？不知道是不是原来研究过 KMP 的缘故，感觉挺容易理解的，就是自己写不出来😂。
method 3
好吧，并不是一定需要 hash 表来判断是否出现重复的字符，感觉下面这段代码才是原汁原味的滑动窗口...1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/* method 3: silding window */
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
int start, end, index, ans, l;
start = end = ans = l = 0;
while(end < len) {
char tmp = s[end];
for(index = start; index < end; index++) {
if(tmp == s[index]) {
start = index + 1;
l = end - start;
break;
}
}
end++;
l++;
ans = max(ans, l);
}
return ans;
}
};
仔细分析一下，好像跟上面的暴力解法是一样的？实际上应该是不一样的，因为上面写的暴力解法里面有很多拷贝字符、判断字符是否重复的操作，但这里并没有。也就是说，这段代码在判断字符是否重复的过程中，其实就已经完成了对字符的拷贝？
567. Permutation in String
Analysis
虽然理解了题意，但是好像没有思路🙃，陷在如何求字符串全排的泥淖中了。
Code
method 1
要用滑动窗口来解题，有一个信息必须要得到，那就是：当两个字符串的每个字符的个数都相等时，一个字符串才是另一个字符串的排列。这样，问题就转化成了判断 s2 是否有子串与 s1 的字符个数相等，这样就可以用两个数组来统计字符个数了。
PS：没想到 vector 可以直接进行比较...1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/* method 1: sliding window */
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n = s1.length(), m = s2.length();
if(n > m) return false;
vector<int> cnt1(26), cnt2(26);
for(int i = 0; i < n; i++) {
cnt1[s1[i] - 'a']++;
cnt2[s2[i] - 'a']++;
}
if(cnt1 == cnt2) return true;
for(int i = n; i < m; i++) {
++cnt2[s2[i] - 'a'];
--cnt2[s2[i - n] - 'a'];
if(cnt1 == cnt2) return true;
}
return false;
}
};
method 2
实际上，这个题也可以只用一个 vector，但是需要一个变量 diff 来保存当前子串是否与 s1 存在字符个数不相等的字符个数。不过，一时半会，好像还是看不明白。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/* method 2: just use one vector */
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n = s1.length(), m = s2.length();
if(n > m) return false;
vector<int> cnt(26);
for(int i = 0; i < n; i++) {
--cnt[s1[i] - 'a'];
++cnt[s2[i] - 'a'];
}
int diff = 0;
for(int c: cnt) {
if(c != 0) diff++;
}
if(diff == 0) return true;
for(int i = n; i < m; i++) {
int x = s2[i] - 'a', y = s2[i - n] - 'a';
if(x == y) continue;
if(cnt[x] == 0) diff++;
cnt[x]++;
if(cnt[x] == 0) diff--;
if(cnt[y] == 0) diff++;
cnt[y]--;
if(cnt[y] == 0) diff--;
if(diff == 0) return true;
}
return false;
}
};
method 3
没想到这题还能用双指针做，好吧，更加有点看不明白了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/* method 3: use tow pointers */
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n = s1.length(), m = s2.length();
if(n > m) return false;
vector<int> cnt(26);
for(int i = 0; i < n; i++) {
cnt[s1[i] - 'a']--;
}
int left = 0;
for(int right = 0; right < m; right++) {
int x = s2[right] - 'a';
cnt[x]++;
while(cnt[x] > 0) {
cnt[s2[left] - 'a']--;
left++;
}
if(right - left + 1 == n) return true;
}
return false;
}
};
Summary
今天的两道题稍微复杂了一点，不是那么好理解，需要多做几次。
