温哥华程序员必看：Apple面试经验 算法题 leetcode 438（Find All Anagrams in a String）python解法分享

搬砖 面经
1

最近在准备面试，尤其对 Apple 这种大公司挺感兴趣。之前我在温哥华一个小公司待过一阵，那边程序员圈子也挺活跃，经常能听到一些面试经验分享。这次就聊聊我准备 Apple 面试时碰到的一些算法问题，特别是 leetcode 438（Find All Anagrams in a String）这个。

438 这题是从一个字符串 s 里找出所有是 p 的字母异位词的子串起始下标。题本身不难理解，但实现起来还是得有点技巧。我最开始直接暴力，把所有长度等于 len(p) 的子串都遍历一遍，再看是不是 p 的字母异位词。简单粗暴，但效率太低了，字符串一长就不行。

Apple Inc Python programming algorithm
Apple Inc Python programming algorithm960×668 176 KB

后来我参考了一些网上的解法，发现可以用滑动窗口加计数数组来做。具体就是一个固定大小（len(p)）的窗口在 s 上移动，同时维护一个长度 26 的计数数组，记录当前窗口里各个字符的数量。每次窗口右移就把新进来的字符加上、把滑出去的字符减掉，再看当前窗口的计数数组和 p 的是不是完全一致。一致就说明找到了一个异位词子串。

这个方法时间复杂度是 O(n)，空间复杂度是 O(1)（因为只有 26 个小写字母），比之前的暴力解法高效得多。下面是我用 Python 写的代码：

def findAnagrams(s, p):
    if len(p) > len(s):
        return []

    p_count = [0] * 26
    s_count = [0] * 26
    result = []

    for ch in p:
        p_count[ord(ch) - ord('a')] += 1

    for i, ch in enumerate(s):
        s_count[ord(ch) - ord('a')] += 1
        if i >= len(p):
            s_count[ord(s[i - len(p)]) - ord('a')] -= 1
        if s_count == p_count:
            result.append(i - len(p) + 1)

    return result

跑一下验证：findAnagrams("cbaebabacd", "abc") 返回 [0, 6]，findAnagrams("abab", "ab") 返回 [0, 1, 2]，跟题目给的样例对得上。

这段代码先统计 p 中每个字符的数量，然后用滑动窗口在 s 上移动，不断更新窗口内的字符数量。当窗口内的计数与 p 相同时，就找到了一个异位词子串起点。

这种题考察的还是对数据结构和算法的理解，以及怎么高效解决问题。就先写到这。

2

补充一个容易混的点：leetcode 386 不是这题。386 是 Lexicographical Numbers，要求按字典序输出 1 到 n，跟异位词一点关系没有，解法是 DFS 或者直接在数字上模拟字典序往下走。我当初刷题的时候就把 386 和 438 的题号记串过，面试时说错题号还挺尴尬的。

顺手贴个 386 的写法对比着看：

def lexicalOrder(n):
    result = []
    cur = 1
    for _ in range(n):
        result.append(cur)
        if cur * 10 <= n:
            cur *= 10
        else:
            while cur % 10 == 9 or cur + 1 > n:
                cur //= 10
            cur += 1
    return result

楼主这个滑动窗口的思路本身没问题，438 这么写是标准解法 haha