leetcode-438. 查找字符串中的所有字母反义词（滑动窗口）
最编程
2024-03-15 13:55:20
...
网络异常，图片无法展示
|
题目链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/
思路
方法一：滑动窗口
直接想法
我们需要找到与p字符串的异位词，所以子串的长度与p字符串相同，我们可以用滑动窗口的方法，统计当前子串的字符数量是否可以跟p字符串匹配
算法
1.遍历数组，在滑动中统计窗口每种字符的数量
2.对比s的滑动窗口中的字符数量是否与p字符串中的字符数量相等
代码示例
func findAnagrams(s, p string) (ans []int) { sLen, pLen := len(s), len(p) if sLen < pLen{ return } var mps, mpt [26]int for i := range p{ mps[s[i] - 'a']++ mpt[p[i] - 'a']++ } if mps == mpt{ ans = append(ans, 0) } for i := range s[:sLen - pLen]{ //维护窗口中所有字符的数量 mps[s[i] - 'a']-- mps[s[i + pLen] - 'a']++ if mps == mpt{ ans = append(ans, i + 1) } } return }
网络异常，图片无法展示
|
复杂度分析
- 时间复杂度： O((n - m) * m) 其中n表示s字符串的长度，m表示p字符串的长度，因为一次滑动窗口对比字符数量的时间是O(m)，总共滑动n - m次
- 空间复杂度：O(26 * 2) 总共开辟两个26长度的数组
方法二：优化滑动窗口
直接想法
在方法一的基础上，发现我们在每次滑动的时候都要对比字符数量是否相等，极大浪费时间，我们其实可以用一个变量记录每次滑动是改变的字符数量d
算法
1.在方法一的基础上，不用对比字符数量，用d记录滑动窗口中不同字符的数量
2.每次滑动的时候，用d记录是否跟上一次的字符数量不同
3.d为0则表示是异位词，记录位置
代码示例
func findAnagrams(s, p string) (ans []int) { sLen, pLen := len(s), len(p) if sLen < pLen{ return } var mps [26]int for i := range p{ mps[s[i] - 'a']++ mps[p[i] - 'a']-- } //记录不同字符的数量 d := 0 for i := range mps{ if mps[i] != 0{ d++ } } if d == 0{ ans = append(ans, 0) } for i := range s[:sLen - pLen] { //不同变相同 if mps[s[i] - 'a'] == 1{ d-- //相同变不同 }else if mps[s[i] - 'a'] == 0{ d++ } mps[s[i] - 'a']-- //不同变相同 if mps[s[i + pLen] - 'a'] == -1{ d-- //相同变不同 }else if mps[s[i + pLen] - 'a'] == 0{ d++ } mps[s[i + pLen] - 'a']++ if d == 0{ ans = append(ans, i + 1) } } return }
网络异常，图片无法展示
|
复杂度分析
- 时间复杂度： O(n) 其中n表示s字符串的长度，遍历p字符串需要O(m)的时间，遍历s字符串需要O(n - m)的时间，刚好加起来是O(n)的时间
- 空间复杂度：O(26) 总共开辟一个26长度的数组
上一篇： 字母异位词分组