字符串的排列
难度 -中等
leetcode567. 字符串的排列
给你两个字符串 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 <= 1e4
s1 和 s2 仅包含小写字母
滑动窗口
这种题目,是明显的滑动窗口算法,相当给你一个 S 和一个 T,请问你 S 中是否存在一个子串,包含 T 中所有字符且不包含其他字符。
题目要求 t 的排列之一是 s 的一个子串。而子串必须是连续的,所以要求的 s 子串的长度跟 t 长度必须相等。
那么我们有必要把 t 的每个排列都求出来吗?当然不用。如果字符串 a 是 b 的一个排列,那么当且仅当它们两者中的每个字符的个数都必须完全相等。
所以,根据上面两点分析,我们已经能确定这个题目可以使用 滑动窗口 + hash表 来解决。
我们使用一个长度和 t 长度相等的固定窗口大小的滑动窗口,在 s 上面从左向右滑动,判断 s 在滑动窗口内的每个字符出现的个数是否跟 t 每个字符出现次数完全相等。
我们定义 need是对 t 内字符出现的个数的统计,定义 wind是对 s 内字符出现的个数的统计。在窗口每次右移的时候,需要把右边新加入窗口的字符个数在 wind 中加 1,把左边移出窗口的字符的个数减 1。如果 need== wind,那么说明窗口内的子串是 t 的一个排列,返回 True;如果窗口已经把 s遍历完了仍然没有找到满足条件的排列,返回 False。
代码演示
public boolean checkInclusion(String t, String s) {
int n = t.length(), m = s.length();
if (n > m) {
return false;
}
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> wind = new HashMap<>();
for (char c : t.toCharArray()){
need.put(c,need.getOrDefault(c,0) + 1);
}
int left = 0;
int right = 0;
int valid = 0;
while (right < m){
//右指针 向右移动 窗口扩大
char c = s.charAt(right);
right++;
//判断新进来的字符 是否是需要的。
if (need.containsKey(c)){
wind.put(c,wind.getOrDefault(c,0) + 1);
if (wind.get(c).equals(need.get(c))){
valid++;
}
}
//判断是否需要缩小窗口。
while (right - left >= n){
//找到直接返回true
if (valid == need.size()){
return true;
}
//如何缩小窗口
char d = s.charAt(left);
left++;
if (need.containsKey(d)){
if (need.get(d).equals(wind.get(d))){
valid--;
}
wind.put(d,wind.get(d) - 1);
}
}
}
return false;
}
进阶优化版
这道题目中说明只有小写字母,因此我们可以用数组代替hash表,进行优化,数组代替hash表有两个好处,
1.优化了常数时间,数组的时间效率高于hash表,
2.优化了内存,数组更省空间,
代码演示:文章来源:https://www.toymoban.com/news/detail-683485.html
public boolean checkInclusion(String t, String s) {
int n = t.length(), m = s.length();
if (n > m) {
return false;
}
int[] need = new int[26];
int[] wind = new int[26];
for (char c : t.toCharArray()){
++need[c - 'a'];
}
int left = 0;
int right = 0;
while (right < m){
//右指针 向右移动 窗口扩大
char c = s.charAt(right);
right++;
//判断新进来的字符 是否是需要的。
if (need[c - 'a'] != 0){
++wind[c - 'a'];
}
//判断是否需要缩小窗口。
while (right - left >= n){
//找到直接返回true
if (Arrays.equals(wind,need)){
return true;
}
//如何缩小窗口
char d = s.charAt(left);
left++;
if (need[d - 'a'] != 0){
--wind[d - 'a'];
}
}
}
return false;
}
上期经典
leetcode76. 最小覆盖子串文章来源地址https://www.toymoban.com/news/detail-683485.html
到了这里,关于leetcode 567. 字符串的排列(滑动窗口-java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!