【Python】辞書の中で1文字ずつ構築できる最長の単語を見つける方法

問題概要

英単語のリスト（英語の辞書を表す配列）が与えられたとき、リスト内の他の単語を使って1文字ずつ構築できる単語のうち、最も長いものを見つける問題を考えます。条件を満たす候補が複数存在する場合は、辞書順で最も小さいものを返します。該当する単語がひとつもない場合は、空文字列を返します。

たとえば、入力が ["h", "he", "hel", "hell", "hello"] の場合を考えてみましょう。「hello」は「h」→「he」→「hel」→「hell」→「hello」という順序で1文字ずつ作ることができるため、出力は "hello" となります。

解法の考え方：トライ木（Trie）を使う

この問題は、接頭辞を共有する文字列を効率よく管理できるトライ木（Trie／前置木）というデータ構造を使うと、スマートに解決できます。各ノードに特殊キー # を持たせ、「そこが単語の終端であるか」をフラグとして記録するのがポイントです。この仕組みにより、「目的の単語の途中にある接頭辞がすべて辞書内の完全な単語になっているか」を簡単にチェックできます。

アルゴリズムの手順

1. trie の初期化： 空のマップ（Pythonの辞書オブジェクト）として trie を用意します。
2. insert(word) の定義： 単語を trie に登録します。
   　・now を trie の先頭に設定する
   　・word の各文字 c について、c が now に存在しなければ now[c] = {'#': False} を作成する
   　・now を now[c] へ移動させ、最後に now['#'] = True として終端をマークする
3. search(word) の定義： その単語が「毎ステップで完全な単語を経由しながら」構築可能かを判定します。
   　・now を trie の先頭に設定する
   　・word の各文字 c について、'#' in now かつ now['#'] が False なら False を返す（途中の接頭辞が完全な単語ではないため）
   　・now を now[c] へ移動させ、最後に now['#'] を返す
4. words 内のすべての単語を insert() で trie に登録します。
5. ans を空文字列で初期化し、words の各 word について、search(word) が True であり、かつ「word の方が ans より長い」または「長さが同じで word の方が辞書順で小さい」場合に ans を word で更新します。
6. 最後に ans を返します。

Pythonでの実装例

class Solution:
    def longestWord(self, words):
        self.trie = {}

        def insert(word):
            now = self.trie
            for c in word:
                if c not in now:
                    now[c] = {'#': False}
                now = now[c]
                now['#'] = True

        def search(word):
            now = self.trie
            for c in word:
                if '#' in now and not now['#']:
                    return False
                now = now[c]
            return now['#']

        for word in words:
            insert(word)

        ans = ""
        for word in words:
            if search(word) and (len(word) > len(ans) or
                                 (len(word) == len(ans) and word < ans)):
                ans = word

        return ans


ob = Solution()
print(ob.longestWord(["h", "he", "hel", "hell", "hello"]))

入力

["h", "he", "hel", "hell", "hello"]

出力

hello

計算量の目安

N を与えられた全単語の総文字数とすると、insert と search はどちらも1単語あたり O(その文字数) で動作するため、処理全体の時間計算量は O(N)、必要なメモリも O(N) となります。ハッシュマップベースの trie を使っているため、事前のソートを行わなくても、辞書順の大小比較だけで正しく「最長かつ辞書順最小」の単語を選び出せる点がこの実装の大きな利点です。