LeetCode：438. Find All Anagrams in a String（找出相同的子串的下标）

阳光穿透心脏的1/2处 2022-04-11 10:53 127阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

### 题目描述： ###

给定一个字符串 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" 的字母异位词。

### java实现方法： ###

/**
         * 判断两个数组是否相同
         *
         * @param sa 数组1
         * @param pa 数组2
         * @return 布尔值
         */
        private boolean isSame(int[] sa, int[] pa) {
            for (int i = 0; i < 26; i++) {
                if (sa[i] != pa[i]) {
                    return false;
                }
            }
            return true;
        }
    
        /**
         * 不按照顺序获取所有下标
         *
         * @param s 字符串s
         * @param p 字符串p
         * @return 链表
         */
        private List<Integer> findAllAnagrams1(String s, String p) {
            List<Integer> result = new ArrayList<>();
            int n = s.length();
            int l = p.length();
            int[] chs = new int[26];
            int[] chp = new int[26];
            for (char ch : p.toCharArray()) {
                chp[ch - 'a']++;
            }
            for (int i = 0; i < n; i++) {
                if (i >= l) {
                    chs[s.charAt(i - l) - 'a']--;
                }
                chs[s.charAt(i) - 'a']++;
                if (isSame(chs, chp)) {
                    result.add(i - l + 1);
                }
            }
            return result;
        }

时间复杂度：  O(n^2)

空间复杂度：  O(n)

--------------------

### Python实现： ###

def find_all_anagrams(self, s: str, p: str) -> List[int]:
            '''
                查找所有的下标
            Args:
                s: 主字符串
                p: 匹配字符串
            Returns:
                所有字符串下标
            '''
            result = []
            len_n = len(s)
            len_p = len(p)
            ch_p = [0] * 26
            ch_s = [0] * 26
            for ch in p:
                ch_p[ord(ch) - ord('a')] += 1
            for i in range(len_n):
                if i >= len_p:
                    ch_s[ord(s[i - len_p]) - ord('a')] -= 1
                ch_s[ord(s[i]) - ord('a')] += 1
                if ch_s == ch_p:
                    result.append(i - len_p + 1)
            return result

时间复杂度：  O(n^2)

空间复杂度：  O(n)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode