字母異位詞分組
來源：力扣（LeetCode）
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。
題目描述：給定一個符串?dāng)?shù)組收恢，將字母異位詞組合在一起武契。字母異位詞指字母相同，但排列不同的字符串挡爵。
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"],
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
解答類似的字母異位等問題竖般，可以考慮引入字典，將KEY值儲存為字符串了讨。
方法一：排序數(shù)組分類
思路
當(dāng)且僅當(dāng)他們的排序字符串相等時捻激，兩個字符串是字母異位詞。
算法
維護(hù)一個映射 ans:{String->List}前计，其中每個鍵K是一個排序字符串胞谭，每個值是初始輸入的字符串列表，排序后等于K男杈。
python
class Solution(object):
def gropAnagrams(self,strs):
ans = collection.defaultdict(list)
for s in strs:
ans[tuple(sorted(s))].append(s)
return ans.values()
復(fù)雜度分析
- 時間復(fù)雜度：O（N K logK）丈屹，其中K是
strs是長度，而K是strs中字符串的最大長度伶棒，當(dāng)我們遍歷每個字符串是旺垒，外部循環(huán)具有的復(fù)雜度為O(N)。然后肤无，我們在O(K logK)的時間內(nèi)對每個字符串排序先蒋。 - 空間復(fù)雜度：O(N K)，排序存儲在
ans中的全部信息內(nèi)容宛渐。
方法二：按計數(shù)分類
思路
當(dāng)且僅當(dāng)他們的字符計數(shù)（每個字符的出現(xiàn)次數(shù)）相同時竞漾，兩個字符串是字母異位詞。
算法
我們可以將每個字符串s轉(zhuǎn)換為字符數(shù)count窥翩，由26個非負(fù)整數(shù)組成业岁，表示a，b寇蚊，c的數(shù)量等笔时。我們使用這些計數(shù)作為哈希映射的基礎(chǔ)。
python
class Solution:
def groupAnagrams(strs):
ans = collections.defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
ans[tuple(count)].append(s)
return ans.values()
復(fù)雜度分析
時間復(fù)雜度：O(NK)O(NK)仗岸，其中 NN 是 strs 的長度允耿，而 KK 是 strs 中字符串的最大長度借笙。計算每個字符串的字符串大小是線性的，我們統(tǒng)計每個字符串较锡。
空間復(fù)雜度：O(NK)O(NK)提澎，排序存儲在 ans 中的全部信息內(nèi)容。
