概要

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"]]

といった結果になります。

Swiftでアナグラムをグルーピングする

概要

詳細