給定一個(gè)字符串?dāng)?shù)組舔痪，將字母異位詞組合在一起静盅。字母異位詞指字母相同究流，但排列不同的字符串。
示例:
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
說明：
所有輸入均為小寫字母榆纽。
不考慮答案輸出的順序仰猖。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/group-anagrams
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)奈籽，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處饥侵。
算法
swift
/**
利用一個(gè)字典維護(hù)異位詞數(shù)組
key：排序之后的異位詞，是異位詞衣屏，排序之后相同躏升，添加到這個(gè)key中的value中
value：異位詞數(shù)組
時(shí)間復(fù)雜度為O(nklogk) n：字符串?dāng)?shù)組長(zhǎng)度，k：字符串?dāng)?shù)組中字符串的最大長(zhǎng)度
空間復(fù)雜度為O(nk)
*/
func groupAnagrams(_ strs: [String]) -> [[String]] {
if strs.count == 0 {
return []
}
if strs.count == 1 {
return [strs]
}
// key: strs中的字符串排序之后的數(shù)據(jù)(是異位詞狼忱，排序之后的字符串相同)膨疏，value：異位詞數(shù)組
var map: [String: [String]] = [:]
for str in strs {
// 字符串排序
let char = String(str.sorted())
// map中沒有這個(gè)key
if !map.keys.contains(char) {
map[char] = [String]()
}
map[char]!.append(str)
}
return Array(map.values)
}
??官方圖解
/**
當(dāng)且僅當(dāng)它們的字符計(jì)數(shù)（每個(gè)字符的出現(xiàn)次數(shù)）相同時(shí)，兩個(gè)字符串是字母異位詞钻弄。
與上面解法有差異的一點(diǎn)是佃却，判斷異位詞的key是以字母出現(xiàn)的次數(shù)
時(shí)間復(fù)雜度為O(nk) n：字符串?dāng)?shù)組長(zhǎng)度，k：字符串?dāng)?shù)組中字符串的最大長(zhǎng)度
空間復(fù)雜度為O(nk)
*/
func groupAnagrams(_ strs: [String]) -> [[String]] {
if strs.count == 0 {
return []
}
if strs.count == 1 {
return [strs]
}
// key: 字符串中每個(gè)字母出現(xiàn)的次數(shù)組成的字符串窘俺，value：異位詞數(shù)組
var map: [String: [String]] = [:]
for str in strs {
// 字母出現(xiàn)的次數(shù)數(shù)組双霍，按字母ASCII索引-'a' 保存對(duì)應(yīng)字母出現(xiàn)次數(shù)
var alphabet = [Int](repeating: 0, count: 26)
let aScalarValue = "a".unicodeScalars.first!.value
for scalar in str.unicodeScalars {
alphabet[Int(scalar.value - aScalarValue)] += 1
}
// map中沒有這個(gè)key
let key = alphabet.description
if !map.keys.contains(key) {
map[key] = [String]()
}
map[key]!.append(str)
}
return Array(map.values)
}
??官方圖解
GitHub：https://github.com/huxq-coder/LeetCode
歡迎star
