古い携帯電話 ガラケーのキーボード
問題
ガラケーのキーボードにおいて、入力値としてキーボード上の押した数字が与えられる(連打回数は無視)。 この時に、押した数字によって得られる単語の組合せの内、辞書に乗っているものを出力する問題。辞書は予め与えられ、データ構造は自由に設定できるものとする。
例: 「２」を押すと'a', ‘b’, ‘c'のどれかとなる。
「３」を押すと’d’, ‘e’, ‘f'のどれかとなる。
解法
全列挙で頑張る
全列挙を考えると、数字に対応する全ての文字のパターンを列挙し、辞書に存在するかを確認する方法が挙げられる。この解法の計算量はO(N4)となる。Nは入力値の桁数であり、１つの数字に対して対応する文字は最大４つなので、全パターンを列挙するためには約N4通り存在するからだ。この解法はとても遅い。
トライ木を用いた解法
上記の解法を少し工夫する。上記の解法で悪い点は、全てのパターンの文字列を生成している点である。中には始めの２文字を選んだ時点で辞書に乗っている単語か否かをチェックすることができれば、その文字は生成する必要がなく途中で処理を止めることができる。枝刈りができるわけだ。これを得意とするのがトライ木である。
事前準備をしてO(N)で解く
最も早い解法は、辞書の中身の単語を予め、ガラケーのキーボードに対応して数字に変換しておくことだ。辞書の単語とその単語を数字に変換したものをHashMapに保存しておけば、入力値の数字から辞書中に存在する単語はO(1)で取得するこができる。
