题目
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例 1：
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例 2：
输入: s1= “ab” s2 = “eidboaoo”
输出: False
提示：
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
分析
难点：
1、怎么巧妙的使用双指针
2、怎么去理解这两个循环
3、怎么去判断多个字符串的（就是第一个循环）
4、第二个循环的下标位和循环的起止条件
// 视频：左吃右拉的概念{https://www.bilibili.com/video/BV15S4y177Zc?spm_id_from=333.337.search-card.all.click&vd_source=3f506dfd7b2a19c74f99363591d70f4c}
// 使用双指针（滑动窗口）+hash表
public boolean checkInclusion(String s1, String s2) {
// 边界判断
if(s1.length() > s2.length()){
return false;
}
// 定义一个列表存储值（存储s1）
int[] counts = new int[26];
for(int i=0; i<s1.length(); i++){
// 这里就开始将双指针的思想用起来
counts[s1.charAt(i)-'a']++;
counts[s2.charAt(i)-'a']--;
}
if(allZero(counts)){
return true;
}
// 开始迭代判断(定位到后面的指针，也方便循环结束判断)
for(int j=s1.length(); j<s2.length(); j++){
counts[s2.charAt(j)-'a']--;
// 因为上面对s2前面的值进行了--
counts[s2.charAt(j-s1.length())-'a']++;
if(allZero(counts)){
return true;
}
}
return false;
}
private boolean allZero(int[] counts){
for(int count:counts){
if(count != 0){
return false;
}
}
return true;
}
解法二
/**
1、变位词：就是各个单词出现的次数一样
2、使用双指针（滑动窗口）+hash表
*/
public boolean checkInclusion(String s1, String s2) {
// 极端判断
if(s1.length()>s2.length()){
return false;
}
Map<Character,Integer> countMap = new HashMap<>();
// 先将s1中的每个字母出现的次数存放到hash表中
for(int i=0; i<s1.length(); i++){
Character ch1 = s1.charAt(i);
Character ch2 = s2.charAt(i);
countMap.put(ch1,countMap.getOrDefault(ch1,0) + 1);
countMap.put(ch2,countMap.getOrDefault(ch2,0) - 1);
}
// 判断一下是不是全是0
if(allZero(countMap)){
return true;
}
// 定义双指针去滑动判断（这里始终是双指针）
for(int j=s1.length(); j<s2.length(); j++){
Character ch1 = s2.charAt(j - s1.length());
Character ch2 = s2.charAt(j);
// 使用滑动窗口
countMap.put(ch1, countMap.getOrDefault(ch1,0) + 1);
countMap.put(ch2, countMap.getOrDefault(ch2,0) - 1);
if(allZero(countMap)){
return true;
}
}
return false;
}
private boolean allZero(Map<Character, Integer> map){
for(Map.Entry<Character, Integer> entry : map.entrySet()){
if(entry.getValue() != 0){
return false;
}
}
return true;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96212.html
