438-找到字符串中所有字母异位词(Find All Anagrams in a String)
发表于：2021-12-03 | 分类： 中等
字数统计: 1.5k | 阅读时长: 7分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string

英文原文

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

 

Constraints:

  • 1 <= s.length, p.length <= 3 * 104
  • s and p consist of lowercase English letters.

中文题目

给定两个字符串 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 * 104
  • s 和 p 仅包含小写字母

通过代码

高赞题解

438. 找到字符串中所有字母异位词

思路一：滑动窗口 + 数组

  1. 因为字符串中的字符全是小写字母，可以用长度为26的数组记录字母出现的次数

  2. 设n = len(s), m = len(p)。记录p字符串的字母频次p_cnt，和s字符串前m个字母频次s_cnt

  3. 若p_cnt和s_cnt相等，则找到第一个异位词索引 0

  4. 继续遍历s字符串索引为[m, n)的字母，在s_cnt中每次增加一个新字母，去除一个旧字母

  5. 判断p_cnt和s_cnt是否相等，相等则在返回值res中新增异位词索引 i - m + 1

代码

[]

class Solution:

    def findAnagrams(self, s: str, p: str) -> List[int]:

        n, m, res = len(s), len(p), []

        if n < m: return res

        p_cnt = [0] * 26

        s_cnt = [0] * 26

        for i in range(m):

            p_cnt[ord(p[i]) - ord('a')] += 1

            s_cnt[ord(s[i]) - ord('a')] += 1

        if s_cnt == p_cnt:

            res.append(0)

        

        for i in range(m, n):

            s_cnt[ord(s[i - m]) - ord('a')] -= 1

            s_cnt[ord(s[i]) - ord('a')] += 1

            if s_cnt == p_cnt:

                res.append(i - m + 1)

        return res

[]

class Solution {

    public List<Integer> findAnagrams(String s, String p) {

        int n = s.length(), m = p.length();

        List<Integer> res = new ArrayList<>();

        if(n < m) return res;

        int[] pCnt = new int[26];

        int[] sCnt = new int[26];

        for(int i = 0; i < m; i++){

            pCnt[p.charAt(i) - 'a']++;

            sCnt[s.charAt(i) - 'a']++;

        }

        if(Arrays.equals(sCnt, pCnt)){

            res.add(0);

        }

        for(int i = m; i < n; i++){

            sCnt[s.charAt(i - m) - 'a']--;

            sCnt[s.charAt(i) - 'a']++;

            if(Arrays.equals(sCnt, pCnt)){

                res.add(i - m + 1);

            }

        }

        return res;

    }

}

复杂度分析

  • 时间复杂度：$O(n)$，for循环有O(n)，数组的长度是常数，所以数组的比较也是常数级别的，那最终的时间复杂度就是$O(n)$

  • 空间复杂度：$O(1)$，需要常数级别的额外空间

思路二：滑动窗口 + 双指针

除了直接比较数组是否相等外，其实还可以用双指针来表示滑动窗口的两侧边界，当滑动窗口的长度等于p的长度时，表示找到一个异位词，两种方式的时间复杂度都是O(n)级别的

先说结论，Python用数组更快一点点（差不太多其实），Java用双指针更快一点，下面是具体步骤：

  1. 定义滑动窗口的左右两个指针left，right

  2. right一步一步向右走遍历s字符串

  3. right当前遍历到的字符加入s_cnt后不满足p_cnt的字符数量要求，将滑动窗口左侧字符不断弹出，也就是left不断右移，直到符合要求为止。

  4. 当滑动窗口的长度等于p的长度时，这时的s子字符串就是p的异位词。

其中，left和right表示滑动窗口在字符串s中的索引，cur_left和cur_right表示字符串s中索引为left和right的字符在数组中的索引

代码

[]

class Solution:

    def findAnagrams(self, s: str, p: str) -> List[int]:

        n, m, res = len(s), len(p), []

        if n < m: return res

        p_cnt = [0] * 26

        s_cnt = [0] * 26



        for i in range(m):

            p_cnt[ord(p[i]) - ord('a')] += 1

        

        left = 0

        for right in range(n):

            cur_right = ord(s[right]) - ord('a')

            s_cnt[cur_right] += 1

            while s_cnt[cur_right] > p_cnt[cur_right]:

                cur_left = ord(s[left]) - ord('a')

                s_cnt[cur_left] -= 1

                left += 1

            if right - left + 1 == m:

                res.append(left)

        return res

[]

class Solution {

    public List<Integer> findAnagrams(String s, String p) {

        int n = s.length(), m = p.length();

        List<Integer> res = new ArrayList<>();

        if(n < m) return res;



        int[] pCnt = new int[26];

        int[] sCnt = new int[26];



        for(int i = 0; i < m; i++){

            pCnt[p.charAt(i) - 'a'] ++;

        }



        int left = 0;

        for(int right = 0; right < n; right++){

            int curRight = s.charAt(right) - 'a';

            sCnt[curRight]++;

            while(sCnt[curRight] > pCnt[curRight]){

                int curLeft = s.charAt(left) - 'a';

                sCnt[curLeft]--;

                left++;

            }

            if(right - left + 1 == m){

                res.add(left);

            }

        }

        return res;

    }

}

复杂度分析

  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(1)$

统计信息

通过次数 提交次数 AC比率
127969 239085 53.5%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
有效的字母异位词 简单
字符串的排列 中等
字符串 哈希表 滑动窗口
上一篇:
437-路径总和 III(Path Sum III)
下一篇:
440-字典序的第K小数字(K-th Smallest in Lexicographical Order)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo