概要
49. Group Anagramsをすっきり解けたので忘れないうちにメモを残しておく。
文字列の一次元配列が与えられた時、各文字列をアナグラムとなる文字列ごとにグループ化し、二次元配列の中に詰めて返却する関数を書く、という要件です。
アナグラムとは、ある言葉や単語の文字を並び替えることによって、別の意味を持つ言葉や単語を作る言葉遊びのことです。
以下が49. Group Anagramsで与えられる入力例と出力例です。
Group Anagrams
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
なお、ここでは以下のような制約が存在します。
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.
詳細
こういった問題が出てくるとアナグラム内の文字列をカタログ(例えば文字列中にaが2回出現しているならa:"2")みたいにカウントしてそれぞれを照会したくなるが、それだと結構長めのコードを書かないといけなくなる。
直前に242. Valid Anagram(与えられた二つの文字列がアナグラムであるかを判定する問題)を解いていたので、これを応用すればいけるじゃん！って気付いてからは早かった。
Valid Anagram
class Solution {
func isAnagram(_ s: String, _ t: String) -> Bool {
guard s.count == t.count else {
return false
}
let sortedS = s.sorted()
let sortedT = t.sorted()
return sortedS == sortedT
}
}
コードは以下の通りです。
Group Anagrams
class Solution {
func groupAnagrams(_ strs: [String]) -> [[String]] {
var anagramGroups:[String:[String]] = [:]
for s in strs{
let sortedString = String(s.sorted())
if var group = anagramGroups[sortedString]{
group.append(s)
anagramGroups[sortedString] = group
}else{
anagramGroups[sortedString] = [s]
}
}
return Array(anagramGroups.values)
}
}
- for文で引数の配列をループします
- ループで各文字列をソートし、そのソートの結果が既に文字列の中にKeyとして存在する場合にはKeyに結びついている既存の配列に追加し、そうでない場合には新しく配列を追加します
- 返すべき値にKeyは必要ないので、作成した
anagramGroupsのValueのみを抽出し、配列に詰めて返します
例えば、"eat","tea","tan"が順番に与えられる場合、
[aet:["eat"]]
[aet:["eat","tea"]]
[aet:["eat","tea"],ant:["tan"]]
といった結果になります。