「力扣」第 438 题：找到字符串中所有字母异位词
- 中文网址：438. 找到字符串中所有字母异位词 ；
- 英文网址：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" 的字母异位词。
说明：这是一道使用滑动窗口解决的典型问题。
方法一：滑动窗口
设置一个 distance 变量，表示二者的差距。
Java 代码：
import java.util.ArrayList;
import java.util.List;
public class Solution3 {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length();
int pLen = p.length();
List<Integer> res = new ArrayList<>();
if (sLen == 0 || pLen == 0) {
return res;
}
char[] charArrayP = p.toCharArray();
int[] pattern = new int[26];
for (char c : charArrayP) {
pattern[c - 'a']++;
}
int distance = pLen;
int left = 0;
int right = 0;
char[] charArrayS = s.toCharArray();
// s[left..right) 包含了 p 中所有的字符
while (right < sLen) {
if (pattern[charArrayS[right] - 'a'] > 0) {
distance--;
}
pattern[charArrayS[right] - 'a']--;
right++;
while (distance == 0) {
if (right - left == pLen) {
res.add(left);
}
if (pattern[charArrayS[left] - 'a'] >= 0) {
distance++;
}
pattern[charArrayS[left] - 'a']++;
left++;
}
}
return res;
}
}Python 代码：
class Solution:
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str 模式串
:rtype: List[int]
"""
from collections import defaultdict
hash = defaultdict(int)
# 滑动窗口的长度
plen = len(p)
# 预处理
for alpha in p:
hash[alpha] += 1
# 滑动窗口的左边界
l = 0
# 滑动窗口的右边界
r = 0
res = []
# 可以认为是两者的差距
distance = plen
while r < len(s):
if hash[s[r]] > 0:
distance -= 1
hash[s[r]] -= 1
r += 1
if distance == 0:
res.append(l)
if r - l == plen:
if hash[s[l]] >= 0:
distance += 1
hash[s[l]] += 1
l += 1
return res
if __name__ == '__main__':
s = "cbaebabacd"
p = "abc"
solution = Solution()
result = solution.findAnagrams(s, p)
print(result)Python 代码：给 p 做字母频率统计，扫过以后，全部一样，就表示找到一个字母异位词。
class Solution:
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
plen = len(p)
slen = len(s)
scnt = [0] * 26
pcnt = [0] * 26
res = []
for alpha in p:
pcnt[ord(alpha) - ord('a')] += 1
for end in range(slen):
if end >= plen:
scnt[ord(s[end - plen]) - ord('a')] -= 1
scnt[ord(s[end]) - ord('a')] += 1
if scnt == pcnt:
res.append(end - plen + 1)
return res
if __name__ == '__main__':
s = "cbaebabacd"
p = "abc"
solution = Solution()
result = solution.findAnagrams(s, p)
print(result)
Python 代码：与上一版代码等价
class Solution:
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
# 滑动窗口的大小
plen = len(p)
slen = len(s)
scnt = [0] * 26
pcnt = [0] * 26
res = []
for alpha in p:
pcnt[ord(alpha) - ord('a')] += 1
for end in range(slen):
scnt[ord(s[end]) - ord('a')] += 1
if end >= plen - 1:
if scnt == pcnt:
res.append(end - plen + 1)
scnt[ord(s[end - plen + 1]) - ord('a')] -= 1
return res
