438. Find All Anagrams in a String
题目描述和难度
- 题目描述：
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 1:
输入: s: "cbaebabacd" p: "abc" 输出: [0, 6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:
输入: s: "abab" p: "ab" 输出: [0, 1, 2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
- 题目难度：简单。
- 英文网址：438. Find All Anagrams in a String 。
- 中文网址：438. 找到字符串中所有字母异位词 。
思路分析
求解关键：
参考解答
参考解答1：我用了比较长的时间才把这个解答写清楚，确实有点绕。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
// 使用滑动窗口的方式解决，标记为简单哦
// s = "cbaebabacd"，p = "abc"
// 参考资料：https://blog.csdn.net/chenwuji91/article/details/52981530
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
// 先考虑特殊情况
if (s == null || s.length() == 0 || p == null || p.length() == 0) {
return res;
}
// 这个 hash 表记录了每个字母出现的频率，即计数值
// ASCII 的长度是 256 位
int[] hash = new int[256];
// 滑动窗口的左边界
int l = 0;
// 滑动窗口的右边界
int r = 0;
// 滑动窗口的长度
int distance = p.length();
for (char c : p.toCharArray()) {
hash[c]++;
}
int sLen = s.length();
while (r < sLen) {
if (hash[s.charAt(r)] > 0) {
// 吸纳进来以后，说明差距减少 1
distance--;
}
// 如果是等于 0 的就说明没有出现在 p 中，也 --，以后左边界扫到它的时候，就知道它不在 p 指定的范围中了
// 不管当前字符在不在 hash 表中，都适用于这个逻辑（听下来想想为什么）
hash[s.charAt(r)]--;
r++;
if (distance == 0) {
// 差距为 0 了，就表示是一个结果，左端点加入结果集
res.add(l);
}
if (r - l == p.length()) {
// 大于等于 0 的，说明字符在 p 中，那些是负的字符说明不在 p 中
if (hash[s.charAt(l)] >= 0) {
// 差距又拉大了 1
// 左端点离开滑动窗口，差距加大 1
distance++;
}
// 左端点离开滑动窗口
// 不管 字符 在不在 p 中，都适用于这个逻辑
hash[s.charAt(l)]++;
l++;
}
}
// System.out.println(Arrays.toString(hash));
return res;
}
// c b a e b a b a c d
// 0 1 2 3 4
public static void main(String[] args) {
Solution solution = new Solution();
String s = "cbaebabacd";
String p = "abc";
List<Integer> anagrams = solution.findAnagrams(s, p);
System.out.println(anagrams);
}
}
参考解答2：和参考解答1 一样的写法，只不过使用了更少的空间。
import java.util.ArrayList;
import java.util.List;
public class Solution2 {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
// 因为题目中说，只有 26 个英文小写字母
int[] chars = new int[26];
if (s == null || s.length() == 0 || p == null || p.length() == 0) {
return res;
}
for (char c : p.toCharArray()) {
chars[c - 'a']++;
}
int left = 0;
int right = 0;
int distance = p.length();
while (right < s.length()) {
if (chars[s.charAt(right) - 'a'] > 0) {
distance--;
}
chars[s.charAt(right) - 'a']--;
right++;
if (distance == 0) {
res.add(left);
}
if (right - left == p.length()) {
if (chars[s.charAt(left) - 'a'] >= 0) {
distance++;
}
chars[s.charAt(left) - 'a']++;
left++;
}
}
return res;
}
}
参考解答3：
import java.util.ArrayList;
import java.util.List;
public class Solution3 {
// 参考了小 Q 的思路，其实还是滑动窗口
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int[] cntp = new int[256];
int[] cnts = new int[256];
for (char c : p.toCharArray()) {
cntp[c]++;
}
int same = 0;
for (int i = 0; i < 256; i++) {
if (cntp[i] == 0) {
same++;
}
}
int plen = p.length();
int slen = s.length();
for (int i = 0; i < slen; i++) {
int curChar = s.charAt(i);
cnts[curChar]++;
if (cnts[curChar] == cntp[curChar]) {
same++;
} else if (cnts[curChar] == cntp[curChar] + 1) {
// 超过了 same 就减 1，再超过反正已经减了 1 ，就不用再减了
same--;
}
// 当 i>= p.lenght() 的时候，左边窗口要考虑左移了
if (i >= plen) {
int deleteChar = s.charAt(i - plen);
cnts[deleteChar]--;
if (cnts[deleteChar] == cntp[deleteChar]) {
same++;
} else if (cnts[deleteChar] == cntp[deleteChar] - 1) {
// 超过了 same 就减 1，再超过反正已经减了 1 ，就不用再减了
same--;
}
}
if (same == 256) {
res.add(i - plen + 1);
}
}
return res;
}
}
参考解答4：和参考解答3 一样的写法，只不过使用了更少的空间。
import java.util.ArrayList;
import java.util.List;
public class Solution5 {
// 这种解法从语义上更好理解一些
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int[] cntp = new int[26];
int[] cnts = new int[26];
int plen = p.length();
int slen = s.length();
// 数组 cntp 在预处理以后是没有变化的
for (int i = 0; i < plen; i++) {
cntp[p.charAt(i) - 'a']++;
}
int same = 0;
for (int i = 0; i < 26; i++) {
if (cntp[i] == 0) {
same++;
}
}
for (int i = 0; i < slen; i++) {
char curChar = s.charAt(i);
cnts[curChar - 'a']++;
if (cnts[curChar - 'a'] == cntp[curChar - 'a']) {
same++;
} else if (cnts[curChar - 'a'] == cntp[curChar - 'a'] + 1) {
same--;
}
if (i >= plen) {
int deleteIndex = i - plen;
char deleteChar = s.charAt(deleteIndex);
cnts[deleteChar - 'a']--;
if (cnts[deleteChar - 'a'] == cntp[deleteChar - 'a']) {
same++;
} else if (cnts[deleteChar - 'a'] == cntp[deleteChar - 'a'] - 1) {
same--;
}
}
if (same == 26) {
res.add(i - plen + 1);
}
}
return res;
}
}
本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0438-find-all-anagrams-in-a-string ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。