Pythonで解く!モールス信号の一意な変換パターンを数える方法

単語のリストが与えられ、それぞれの単語は各文字のモールス符号を連結したものとして表現できるとします。例えば、「cba」という単語は「-.-..--...」と書けます。これは「-.-.」+「-...」+「.-」を順に連結したものです。このような連結結果を「単語の変換(transform)」と呼びます。

国際モールス符号では、アルファベットの各文字がドット(.)とダッシュ(-)の列に標準的にマッピングされています。たとえば「a」は「.-」、「b」は「-...」、「c」は「-.-.」のように対応します。

英語アルファベット26文字すべての対応表は次のとおりです。

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

問題の例

入力が ["gin", "zen", "gig", "msg"] の場合、出力は 2 になります。各単語の変換結果は以下のようになります。

• "gin" → "--...-."
• "zen" → "--...-."
• "gig" → "--...--."
• "msg" → "--...--."

4つの単語が与えられていますが、実際に現れる変換パターンは2種類だけです。そのため、一意な変換の数である答えは2となります。

解法のアプローチ

この問題はセット(set)を使うことでシンプルに解けます。セットは重複を自動的に排除してくれるため、すべての単語をモールス符号に変換してセットへ登録すれば、最終的なセットのサイズがそのまま一意な変換の数になります。手順は以下のとおりです。

• morse_codes に26文字分のモールス符号リストを定義します。
• 空のセット s を用意します。
• words 内の各単語 word に対して以下を実行します。
  • temp を空文字列として初期化します。
  • word 内の各文字 c に対して、temp := temp + morse_codes[ord(c) - 97] を実行します。c の ASCII コードから 97 を引くことで、小文字 'a' がインデックス0に対応づけられます。
• 完成した temp をセット s に追加します。
• 最後に s のサイズを返します。

Pythonでの実装例

class Solution:
    def uniqueMorseRepresentations(self, words):
        morse_codes = [".-","-...","-.-.","-..",".","..-.","--.",
                        "....","..",".---","-.-",".-..","--","-.",
                        "---",".--.","--.-",".-.","...","-","..-",
                        "...-",".--","-..-","-.--","--.."]
        s = set()
        for word in words:
            temp = ''
            for c in word:
                temp += morse_codes[ord(c) - 97]
            s.add(temp)
        return len(s)

ob = Solution()
print(ob.uniqueMorseRepresentations(["gin", "zen", "gig", "msg"]))

入力

["gin", "zen", "gig", "msg"]

出力

2

計算量について

時間計算量は O(S) です。ここで S はすべての単語に含まれる文字数の合計を指します。各文字ごとにモールス符号の参照と連結が定数時間で行えるためです。空間計算量も同様に O(S) となり、生成されたモールス符号文字列をセットに保持する分のメモリが必要になります。