字符串的排列Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。
换句话说,s1 的排列之一是 s2 的 子串 。
示例 1:
输入:s1 = "ab" s2 = "eidbaooo"
输出:true
解释:s2 包含 s1 的排列之一 ("ba").
示例 2:
输入:s1= "ab" s2 = "eidboaoo"
输出:false
提示:
- 1 <= s1.length, s2.length <= 104
- s1 和 s2 仅包含小写字母
# 思路
滑动窗口
# 解法
class Solution {
public boolean checkInclusion(String s1, String s2) {
int sz = s2.length();
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for(char c : s1.toCharArray()){
need.put(c, need.getOrDefault(c,0)+1);
}
int left = 0, right = 0;
int valid = 0;
while(right < sz){
//进来的字符
char c = s2.charAt(right);
right++; //扩大窗口
//改变窗口状态
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c))) valid++;
}
//判断是否要收缩
while(valid == need.size()){
//子串包含s1的全部字符 且 长度相等 即 满足题意
if(right - left == s1.length()) return true;
//要移出的字符
char d = s2.charAt(left);
left++; //缩小窗口
//改变窗口状态
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))) valid--;
window.put(d, window.getOrDefault(d,0)-1);
}
}
}
return false;
}
}
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
31
32
33
34
35
36
37
38
39
40
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
31
32
33
34
35
36
37
38
39
40
# 总结
- 分析出几种情况,然后分别对各个情况实现