1

【小馬的LeetCode練功坊】兩道anagram問題- 49. Group Anagrams 和 438. Find All Anagrams in a String

anagram是小馬做題目才學到的新單字，

一、把重組字放在一起

``````Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
``````

python程式碼，152ms

`itertools`模組內的`groupby`函數可以把相同性質的元素放在一起，

``````from itertools import groupby

def grouping(arr, KEY_FUNC):
A = sorted(arr, key = KEY_FUNC)
return [list(g) for k, g in groupby(A,key=KEY_FUNC)]

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
return grouping(strs, sorted(x))
``````

二、找出字串中所有重組字

``````Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
index 0開頭的子字串是"cba"，是"abc"的重組字。
index 6開頭的子字串是"bac"，是"abc"的重組字。
``````

python程式碼暴力解，8768 ms

``````class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
P = sorted(p)
ans = []
for i in range(len(s)-len(p)+1):
if(sorted(s[i:i+len(p)])==P):
ans.append(i)
return ans
``````

python程式碼用Counter，164 ms

``````from collections import Counter
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
P = Counter(p)
subStr = Counter(s[:len(p)])
ans = [0] if subStr == P else []
for i in range(len(s)-len(p)):
subStr[s[i]]-=1
if subStr[s[i]]==0: #如果元素個數為0，記得刪除
del subStr[s[i]]
subStr[s[i+len(p)]]+=1
if(subStr == P):
ans.append(i+1)
return ans
``````