LeetCode-567-字符串的排列

LeetCode-567-字符串的排列

给定两个字符串 s1s2,写一个函数来判断 s2 是否包含 s1 的排列。

换句话说,第一个字符串的排列之一是第二个字符串的子串。

示例1:

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

示例2:

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

注意:

  1. 输入的字符串只包含小写字母
  2. 两个字符串的长度都在 [1, 10,000] 之间

解题思路

方法1、滑动窗口(套模版):

https://leetcode-cn.com/problems/permutation-in-string/solution/wo-xie-liao-yi-shou-shi-ba-suo-you-hua-dong-chuang/

方法2、滑动窗口(数组优化):

由于都是小写字符,所以初始化两个数组作为need和window,剩余步骤依旧按照模版走,详见注释。

Java代码1

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
class Solution {
public boolean checkInclusion(String s1, String s2) {
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;
int start=0,len =Integer.MAX_VALUE;
while(right < s2.length()){
char c = s2.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if((int)window.get(c) ==(int) need.get(c)){
valid++;
}
}
while(right-left == s1.length()){
if(valid == need.size()){
return true;
}
char d = s2.charAt(left);
left++;
if(need.containsKey(d)){
if((int)window.get(d) == (int)need.get(d)){
valid--;
}
window.put(d,window.get(d)-1);
}
}
}

return false;
}
}

Java代码2

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
41
42
class Solution {
public boolean checkInclusion(String s1, String s2) {
char[] arrS1 = s1.toCharArray();
char[] arrS2 = s2.toCharArray();
int[] needs = new int[26];
int[] window = new int[26];
int cntChar = 0; // 有效字母个数(不同的字母个数)
for(char c: arrS1){
if(needs[c-'a']==0) cntChar++;// 如果该字母第一次出现,记录下来
needs[c-'a']+=1;
}
int left = 0;
int right = 0;
int valid = 0;
while(right < arrS2.length){
char c = arrS2[right];
// 对窗口内数据进行一系列更新
window[c-'a']+=1;
if(window[c-'a']==needs[c-'a']){
valid++;
}
// 当窗口扩散到包含s1时,进行左边界收缩
while(cntChar==valid){
// 如果窗口大小为s1的长度,则说明找到了
if(right-left+1==arrS1.length){
return true;
}

char d = arrS2[left];
// 窗口缩小,对应字符出现次数-1
window[d-'a']-=1;
// 当字符次数小于s1中字符出现次数时,则说明窗口达到包含s1字符的最小窗口
if(window[d-'a']<needs[d-'a']){
valid--;
}
left++;
}
right++;
}
return false;
}
}
打赏了解一下?
0%