LeetCode - 字母異位詞分組 (Group Anagrams)
題目描述:
給定一個字符串數組,將異位詞分組。異位詞是指包含相同字母但順序不同的字符串。
範例:
1
2
輸入:["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
解法思路:
- 我們可以通過對每個字符串進行排序,將異位詞變成相同的排序結果,然後將這些相同的結果分組。
- 使用一個哈希表來儲存排序後的結果作為鍵,異位詞組作為值。
範例代碼(Python):
1
2
3
4
5
6
7
8
from collections import defaultdict
def groupAnagrams(strs):
anagrams = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
anagrams[key].append(s)
return list(anagrams.values())
時間複雜度:
O(n * k log k),其中 n
是字符串數組的長度,k
是字符串的最大長度。排序每個字符串的時間複雜度為 O(k log k)。
本文章以 CC BY 4.0 授權