素人がGoogleが提供している学習用教材Google Tech Dev Guideに取り組んだが、門外漢なので英語で読みながらだと内容が入ってこず。一旦すべて日本語訳してから読んだほうが効率が良いだろうということで和訳した。
どなたかの参考になれば。
今回取り組んだのは以下：
■タイトル
Former Coding Interview Question: Find longest word in dictionary that is a subsequence of a given string
やったこと
１、まずは自分で解く
・Python3.6で実施
・特に工夫もせずリンク先のGreedy algorithmに相当する物を作った
def find_longest_word_in_string(letter, words):
i = 0
ok = ""
l = len(letter) - 1
for w in words:
j = 0
while j < l:
if w[0] == letter[j]:
j += 1
w = w[1:]
else:
j +=1
if w == "":
if len(ok) < len(words[i]):
ok = words[i]
i += 1
return(ok)
S = "abppplee"
D = ["jam", "jamboleeee", "able", "ale", "apple", "bale", "kangaroo"]
result = find_longest_word_in_string(S, D)
print(result)
２、解説の読み解き
以下解説の和訳。
■解説
課題の解決アプローチとしては様々な方法が考えられる
(例えば適用できるアルゴリズムは複数ある)。
つまりあなたの問題解決能力と知識が試される。
■力づくの解法
文字列Sから2^nの考えられる部分文字列をすべて生成し、辞書Dの単語にマッチするかを確認。ちょっとした最適化として検索を効率化するため比較対象の文字列がハッシュテーブルかプレフィックス木で表されるようにする。
■貪欲法で辞書のそれぞれの単語についてチェックする
辞書Dの単語wがSの部分文字列となるかどうかを貪欲法で確認することができる。Sをw[0]について先頭からスキャンする。Sの中にw[0]が見つかったら、続いてw[1]についてw[0]を見つけた位置からスキャンしていき、S全体をスキャンし終わるか、wに含まれる文字を全て見つけるまで続ける。
Dに含まれる単語の長さで降順ソートしてから上記の手順を実施し、Sの部分文字列となる最初の単語を検出結果とすることができる。実行時間は辞書に含まれる単語の数WとSに含まれる文字数NからO(N*W)となる。
Dに含まれる単語の長さがSの長さにNに近い場合実行時間O(N*W)は漸近的に最適となる(入力がO(N*W)のため)。しかし、最悪の場合である文字列Sが長くDに含まれる単語がとても短い場合は最適とは程遠い。
辞書に含まれる全単語の文字の合計長さをLとする。この場合、計算時間のベストケースは(単語がSより短い場合を考える)O(N+L)となる。しかし、上記のアルゴリズムの実行時間はO(N*W)であり、辞書に含まれる単語が一定の小さい長さの場合はO(N*L)になる場合がある。
■貪欲法の改善方法
辞書の単語wをチェックするには結局のところwに含まれる文字cについて前に文字がSとマッチした位置jよりも大きなS[i]==cとなる最小のiがわかる必要があるということに気づいて欲しい。貪欲法はこのiを何も考えずにスキャンするため明らかに遅い。
Sを前処理することでそのような操作をかなり早くすることができる。文字のマップを作る->文字のありかでソートしたリストを作る。
例えばS == "abppplee"の場合:
a -> [0]
b -> [1]
p -> [2, 3, 4]
l -> [5]
e -> [6, 7]
"ひとつ前にマッチした文字はXだった、次の文字Yはどこにマッチするか?"を知りたい時Yをマップの中から探して続いて二分探索でリストの中からXの位置の最小の番号を見つけるか、それが存在しないことがわかる(その場合その単語はSに含まれる順番通りではない)。
この方法ではDに含まれる文字につき一回の二分探索を必要とする。よってこの場合Sの前処理にはO(N)だけしかかからないので、全体の処理時間はO(N+logN)＊1となり起こりうるベストの処理時間に近づく。
＊1、二分探索の実行時間のためlogの底は2。
より進んだアプローチ：これは古典的な"successor-value"問題であるため、検索をさらに高速に実行できる特殊なデータ構造が存在することに気付くかもしれない。例えばvEB treeを使うと実行時間はO(N+L*loglogN)に改善する。
■小さいサイズの文字列へのO(N+L)の最適なアプローチ（ここ、よくわからず）
文字列のサイズがa-zまたは一定の小さい数だけならば、前出のO(N+L)の実行時間で解くことができる。
現実の実行時間はO(N*A+L)で、Aはアルファベットの数である。スパースな表現＊2を作成する代わりに(you could make it dense)。←よくわからず。
p -> [2, 3, 4] とする代わりにp -> [2, 2, 3, 4, -1, -1, -1, -1] とでき、i番目のインデックは直接クエリへの回答を生成する。この方法では文字毎にO(N)のスペースを必要とし(合計でO(NA))、前処理に時間がかかる。そのため大きな文字列には適さない。
＊2、データを表現するための辞書を用意し、その要素のできるだけ少ない組み合わせでデータを表現する?
■どのような文字列にも最適の方法
単語毎に処理をする代わりにすべての単語を同時に処理する。
まずDに含まれる単語wそれぞれについてwと0を含むタプルを作る(例：(w,0))。この数字はSの中に見つかったwに含まれる文字であり、したがって最初は一つも見つかっていない。タプルtについてタプルの単語をt.w、タプルに含まれる数をt.i(インデックスなので)とする。
単語をt.w[t.i]でグループにする(t.iの初期値は0なので、初期値は最初の文字)。例えば例ではD = {"able", "ale", "apple", "bale", "kangaroo"}なので、
a -> [("able", 0), ("ale", 0), ("apple", 0)]
b -> [("bale", 0)]
k -> [("kangaroo", 0)]
ここで行っているのは次にSの中で見つかる可能性のある文字についてどの単語について調査をするかを示している。
Sについて一文字ずつスキャンする。もしスキャンした文字がcの場合はmap[c]に含まれる各タプルについてt.iを1インクリメントして、map[t.w[t.i]]に移す＊3。t.i == t.w.lengthの場合は特別で単語"found"リストに移す。最終的なプログラムの出力はfoundリスト中の最も長い単語である。
＊3、自分用メモ、単語ableの場合で検索文字がaの場合は("able",1)としてbのグループに移し、b->[("bale", 0), ("able", 1)]となる。
３、解答例を写経
画面を見ながら写経しコメントを入れて動作確認。
(元の解答例は３５行目のif文のインデントを修正する必要あり)
#!/usr/bin/env python
import collections
import sys
import logging
logging.basicConfig(level = logging.DEBUG, format = "%(asctime)s - %(levelname)s - %(message)s")
logging.disable(logging.DEBUG)
def find_longest_word_in_string(letters, words):
letter_positions = collections.defaultdict(list)
#初期化不要のリストを作成するため。defaultdictを使用。
for index, letter in enumerate(letters):
letter_positions[letter].append(index)
#lettersから文字を辞書のkeyとして取り出し。
#lettersの中のletterの位置を辞書にリストで格納。
#keyはletter。
for word in sorted(words, key=lambda w: len(w), reverse=True):
#wordsの中の単語を長さで降順ソート
pos = 0
for letter in word:
logging.debug("word is {}, letter is {}." .format(word, letter))
if letter not in letter_positions:
break
#文字がletter_positionsになければbreak
possible_positions = [p for p in letter_positions[letter] if p >= pos]
#pは対象のletterの位置。forループ内の途中のif文がbreakされてもposは加算されるため、
#次の文字が判定対象になる。
logging.debug("possible_positions are {}." .format(possible_positions))
logging.debug("pos is {}." .format(pos))
if not possible_positions:
break
logging.debug("possible_positions[0] is {}." .format(possible_positions[0]))
pos = possible_positions[0] + 1
#possible_positin[0]はletterの位置を格納したリストの先頭の数字を返す。
#↑により、lettersの中で判定対象の文字を現在のletterより後の文字とする。
#例：letters = "aaapplle"、word = "apple"の場合、
#一周目のループのletterは"a"のため、possible_positions = (0, 1, 2)
#次のループのposは0 + 1 = 1
#次のループではletterは"p"のため、possible_positions = (3, 4)
#次のループのposは3 + 1 = 4
#次のループではletterは"p"だが、p >= posより4以上でが条件のため、
#possible_positions = (4)
#単語に含まれる文字が無くなるまでforが回った場合breakされず、その単語を返す。
else:
return word
#print(find_longest_word_in_string(sys.argv[1], sys.argv[2:]))
#コマンドラインから文字列と単語を指定して実行。
if __name__ == '__main__':
letters = "abppplee"
words = ["able", "ale", "apple", "bale", "kangaroo"]
print(find_longest_word_in_string(letters, words))
#コマンドラインから直接スクリプトファイルを実行した場合は「__name__という変数（属性）の中に自動的に
# __main__を代入する」操作が一番はじめにで行われる。
４、リンク先の解説を読んでざっくり振り返り
・文字数×単語の数だけ時間がかかる、遅い
・せめて単語の長さでソートして途中でbreakすべきだった
・データの前処理の工夫が大事