動機

想起優化LC 127的過程

Problem

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.

 

Example 1:

Input: s = cbaebabacd, p = abcOutput: [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 = abOutput: [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.

Sol1

就是sliding windows，但是window裡面連不在pattern中的也一起放進來，導致每次檢查就要先排除不在pattern的字元，這樣會拖慢執行時間

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ret = []
        i = 0
        j = len(p)
        #print(p)
        p = Counter(list(p))
        cnt = dict(Counter(s[i:j]))
        #print(cnt)
        while i < j and j <= len(s):
            if all([(k not in p and v == 0) or (k in p and p[k] == v) for (k,v) in cnt.items()]):
                ret.append(i)
            
            if j < len(s):
                if s[j] not in cnt:
                    cnt[s[j]] = 1
                else:
                    cnt[s[j]] += 1
                j += 1
            
            cnt[s[i]] -= 1
            i += 1
            #print(i,j,cnt)
        return ret

Sol2

在生紀錄window的counter時不把不需要的字元放進去，這樣除了讓執行效率提升，還讓程式變簡單了

這讓我突然想到之前寫BFS(LC 127)是一次把狀態生到需要的狀態，而不是去檢查能不能從起點轉移到下一個狀態，讓效率上升

這裡是不讓不需要的東西進入需要多次檢查的狀態中，這兩個對我來說都有一點類似的感覺

另外關於Counter有兩件事

  1. Counter有預設值!!
  2. 可以直接比
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ret = []
        i = 0
        j = len(p)
        #print(p)
        p = Counter(list(p))
        cnt = Counter([c for c in s[i:j] if c in p])
        while i < j and j <= len(s):
            if cnt == p:
                ret.append(i)
            
            if j < len(s) and s[j] in p:
                cnt[s[j]] += 1
            j += 1
            
            if s[i] in p:
                cnt[s[i]] -= 1
            i += 1
            #print(i,j,cnt)
        return ret