class Solution {
public:
vector<int> findAnagrams(string s, string p) {
}
};
剑指 Offer II 015. 字符串中的所有变位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
示例 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" 的变位词。
提示:
1 <= s.length, p.length <= 3 * 104s 和 p 仅包含小写字母
注意：本题与主站 438 题相同： https://leetcode.cn/problems/find-all-anagrams-in-a-string/
原站题解
python3 解法, 执行用时: 104 ms, 内存消耗: 15.6 MB, 提交时间: 2022-11-23 11:31:53
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
if s_len < p_len: return []
ans = []
count = [0] * 26
for i in range(p_len):
count[ord(s[i]) - 97] += 1
count[ord(p[i]) - 97] -= 1
differ = [c != 0 for c in count].count(True)
if differ == 0:
ans.append(0)
for i in range(s_len - p_len):
if count[ord(s[i]) - 97] == 1: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i]) - 97] == 0: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
differ += 1
count[ord(s[i]) - 97] -= 1
if count[ord(s[i + p_len]) - 97] == -1: # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i + p_len]) - 97] == 0: # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从相同变得不同
differ += 1
count[ord(s[i + p_len]) - 97] += 1
if differ == 0:
ans.append(i + 1)
return ans
python3 解法, 执行用时: 112 ms, 内存消耗: 15.6 MB, 提交时间: 2022-11-23 11:21:55
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
if s_len < p_len:
return []
ans = []
count = [0] * 26
for i in range(p_len):
count[ord(s[i]) - 97] += 1
count[ord(p[i]) - 97] -= 1
differ = [c != 0 for c in count].count(True)
if differ == 0:
ans.append(0)
for i in range(s_len - p_len):
if count[ord(s[i]) - 97] == 1: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i]) - 97] == 0: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
differ += 1
count[ord(s[i]) - 97] -= 1
if count[ord(s[i + p_len]) - 97] == -1: # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i + p_len]) - 97] == 0: # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从相同变得不同
differ += 1
count[ord(s[i + p_len]) - 97] += 1
if differ == 0:
ans.append(i + 1)
return ans
golang 解法, 执行用时: 0 ms, 内存消耗: 4.9 MB, 提交时间: 2022-11-23 11:21:27
func findAnagrams(s, p string) (ans []int) {
sLen, pLen := len(s), len(p)
if sLen < pLen {
return
}
count := [26]int{}
for i, ch := range p {
count[s[i]-'a']++
count[ch-'a']--
}
differ := 0
for _, c := range count {
if c != 0 {
differ++
}
}
if differ == 0 {
ans = append(ans, 0)
}
for i, ch := range s[:sLen-pLen] {
if count[ch-'a'] == 1 { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
differ--
} else if count[ch-'a'] == 0 { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
differ++
}
count[ch-'a']--
if count[s[i+pLen]-'a'] == -1 { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
differ--
} else if count[s[i+pLen]-'a'] == 0 { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
differ++
}
count[s[i+pLen]-'a']++
if differ == 0 {
ans = append(ans, i+1)
}
}
return
}
golang 解法, 执行用时: 4 ms, 内存消耗: 4.9 MB, 提交时间: 2022-11-23 11:21:06
func findAnagrams(s, p string) (ans []int) {
sLen, pLen := len(s), len(p)
if sLen < pLen {
return
}
var sCount, pCount [26]int
for i, ch := range p {
sCount[s[i]-'a']++
pCount[ch-'a']++
}
if sCount == pCount {
ans = append(ans, 0)
}
for i, ch := range s[:sLen-pLen] {
sCount[ch-'a']--
sCount[s[i+pLen]-'a']++
if sCount == pCount {
ans = append(ans, i+1)
}
}
return
}