438. Find All Anagrams in a String

題目
思路：怎麼判斷兩個字串是不是 anagram?

可以把兩個字串都做排序，再看看是否相等，但這樣每次都要多花 O(n) 時間
可以計算每個字母出現的頻率，再看看兩個字串的計算結果是否相等。雖然單獨算也是要 O(n)，但假如搭配 sliding window 移動的時候一個個字母加入計算，就不會有額外的時間複雜度

Python 3 solution

def findAnagrams(self, s: str, p: str) -> List[int]:
    p_len = len(p)
    if p_len > len(s):
        return []

    target_freq = defaultdict(int)  # Character frequency of possible anagram.

    # Character frequency of `p`.
    p_freq = defaultdict(int)
    for c in p:
        p_freq[c] += 1
    
    res = []
    for i in range(len(s)):
        # 把超過 p 長度的部分扣掉，維持 window 寬 (想像 window 往右，這邊移掉左邊一格)
        if i >= p_len:
            target_freq[s[i - p_len]] -= 1
            if target_freq[s[i - p_len]] == 0:
                del target_freq[s[i - p_len]]  # 個數減為 0 的話記得要把整個 key 拿掉，不然不可能會跟 `p_freq` 相等

        target_freq[s[i]] += 1  # Frequency 計算：加入當前字元 (`i` 是 sliding window 最右邊的 index)
        if target_freq == p_freq:
            res.append(i - p_len + 1)  # 加入 sliding window 起始點到答案中
    return res

P.S.
字母頻率計算也可以用 collections.Counter，跟 defaultdict(int) 使用方法一樣，範例：

>>> import collections
>>> c = collections.Counter('geeeg')
>>> c
Counter({'e': 3, 'g': 2})
>>> c['t'] += 1
>>> c
Counter({'e': 3, 'g': 2, 't': 1})

collections.Counter 建構子可以傳入任何 iterable

# hash table, sliding window, string

438. Find All Anagrams in a String

評論

分類

標籤雲

最新文章

彙整

標籤

最新文章

彙整

標籤

Your browser is out-of-date!