LeetCode「49. Group Anagrams」をC#で解いてみました

概要

エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。

問題

49. Group Anagrams

文字列strsの配列が与えられたとき、アナグラムをグループ化しなさい。答えはどのような順序でも返すことができる。
アナグラムとは、異なる単語やフレーズの文字を並べ替えて作られた単語やフレーズのことで、通常、元の文字をすべて一度だけ使用します。

制約

1 <= strs.length <= 10⁴
0 <= strs[i].length <= 100
strs[i] は小文字の英字で構成されます

解説

まず初めにアナグラム毎にまとめた文字列をグループ化するためにDictionary<List<string>> を用意して、渡された文字列を順番に処理していくためのforeachを用意します。

GroupAnagrams

// アナグラムのグループ化した格納場所を用意
var dictionary = new Dictionary<string, List<string>>();

// 渡された文字列を一つずつ処理する
foreach (var word in strs)
{
}

次に単語に使用されている文字を判別するために、昇順に並び替えます。
eat もtea も文字を昇順に並び替えればaet となるため同じ文字を使用したアナグラムと判別が可能です。

GroupAnagrams

// 渡された文字列を一つずつ処理する
foreach (var word in strs)
{
    // 文字列を昇順に並べ替える
    char[] wordCharacters = word.ToCharArray();
    Array.Sort(wordCharacters);
    string sortedWord = new string(wordCharacters);
}

確認対象の単語が既出の単語のアナグラムではない場合、新しいグループとするため並び替えた文字をキーとしてリストを作成します。
その後、共通処理として並び替えた文字をキーとして単語をリストに追加し、次の単語の確認処理に入ります。

GroupAnagrams

// 渡された文字列を一つずつ処理する
foreach (var word in strs)
{
    // 文字列を昇順に並べ替える
    char[] wordCharacters = word.ToCharArray();
    Array.Sort(wordCharacters);
    string sortedWord = new string(wordCharacters);

    // 対象の単語が既出の単語のアナグラムではなかった場合リストを作成
    if (!dictionary.ContainsKey(sortedWord))
    {
        dictionary.Add(sortedWord, new List<string>());
    }

    // 単語をアナグラムグループに追加
    dictionary[sortedWord].Add(word);
}

最後にアナグラム毎にグループ化したリストを作成し返して終了です。

GroupAnagrams

// 単語のグループをリスト化して返す
return new List<IList<string>>(dictionary.Values);

ソースコード

Solution.cs

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs)
    {
        // 制約がなかった場合の例外処理
        if (strs == null || strs.Length == 0)
        {
            return new List<IList<string>>();
        }

        // アナグラムのグループ化した格納場所を用意
        var dictionary = new Dictionary<string, List<string>>();

        // 渡された文字列を一つずつ処理する
        foreach (var word in strs)
        {
            // 文字列を昇順に並べ替える
            char[] wordCharacters = word.ToCharArray();
            Array.Sort(wordCharacters);
            string sortedWord = new string(wordCharacters);

            // 対象の単語が既出の単語のアナグラムではなかった場合リストを作成
            if (!dictionary.ContainsKey(sortedWord))
            {
                dictionary.Add(sortedWord, new List<string>());
            }

            // 単語をアナグラムグループに追加
            dictionary[sortedWord].Add(word);
        }

        // 単語のグループをリスト化して返す
        return new List<IList<string>>(dictionary.Values);
    }
}

概要

問題

制約

解説

ソースコード

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル