Leetcode題解 Python & C#：五月挑戰DAY17 Find All Anagrams in a String

給一個字串 s 跟 非空字串 p 。要從 s 中找出所有 p 字謎的的起始位置。
(字謎是所有字母都出現一次，連續出現但順序可以變動)

如果順序不重要，那麼用 hashtable 記下哪些字母出現與次數及可。

從 s 開頭，依序匹配，是否在hashtable中及目前有可匹配的次數嗎？如果有，該字母的可匹配的次數 – 1，匹配長度 +1。
如果沒有，用匹配長度把最前方的已匹配字母放回hashtable所對應的次數，直到匹配或是匹配長度歸零為止。

如果匹配長度與 p 長度相同，則回推開始位置放入 result 中。

Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        count = Counter(p)
        match_len = 0
        p_len = len(p)
        result = []
        for i in range(len(s)):
            c = s[i]
            while match_len and (c not in count or count[c] == 0):
                count[s[i-match_len]] += 1
                match_len -= 1
            
            if c in count and count[c] > 0:
                count[c] -= 1
                match_len += 1
                if match_len == p_len:
                    result.append(i-p_len+1)
                        
        return result

C#

public class Solution {
    public IList FindAnagrams(string s, string p) {
        var count = new Dictionary();
        foreach(char c in p)
        {
            if(count.ContainsKey(c))
                count[c] += 1;
            else
                count[c] = 1;
        }
        var result = new List();
        int match_len = 0;
        for(int i = 0; i < s.Length; i ++)
        {
            char c = s[i];
            bool hasKey = count.ContainsKey(c);
            while(match_len > 0 && (!(hasKey) || count[c] == 0))
            {
                count[s[i - match_len]] += 1;
                match_len -= 1;
            }   
            if(hasKey && count[c] > 0)
            {
                match_len += 1;
                count[c] -= 1;
                if(match_len == p.Length)
                    result.Add(i - match_len + 1);
            }
        }
        return result;
    }
}