こんにちは
今回の学びは
・まぁ、つかえるぞ これDP問題を解くときの考え方マニュアル
・dpもしくは配列へのアクセス関数を作ること
問題は。。。
まずは入出力をしっかりおさえましょう。
入力はとある文字列と辞書で、その文字列は辞書の中の文字列たちだけで構成できるかどうか？という問題
総当りでかんがえると、これは辞書から攻めるのか、とある文字列から攻めるのか
悩むところですが、これはとある文字列からかんがえます。
leetcodeという文字列は0個で区切ると -> 1
1個で区切ると-> 2
2子で区切る-> 3
..
N-1個で区切ると -> N
で 1 + 2 + ... + N だから N * N/2 の文字列が作れる。
（1 + 2 + 3 + .... 97 + 98 + 99の場合は 100 * 50 だから 5000くらい）
それを辞書に称号する作業は
辞書の数をmとすると N*N/2 かける m とうことになりますね。
O(N* N/2 * M )といことでう、 O(N**2 * m) ｍがn同等に大きいとすると O(N**3)の
アルゴリズムということなりまして
別のもっと速い、効率的な方法をさがそうといことになります。
さて、DP問題を解くときの考え方マニュアルによると次に考えたいのは
２，問題を小さく（往々に入力を小さく）して、その答えが次にその入力を大きくしたときのベースとしてつかえるか？をかんがえる。
ということなので
leetcodeでしょ。たとえば入力がl だけだったら？
辞書にそんなのないから作れない、
iという操作パスで一文字づつふやしていくと、leetまでいってはじめてyes だ。
しかしその結果はL(i-1)の結果には起因しなさそうだ。
ふーんでも、操作パスをもう一個ふやしてi, jで先頭と終了位置をあらわし、そこの
でてきた文字列が辞書にあるかのyes|noをだしていって、yesであれば、その文字列数を
さかのぼった位置の結果によってこれまで連続で辞書に存在ししているかがわかる。
つまり
漸化式がつくれそうで
L(i) = 現在の文字列が存在するならば L( i - 存在した文字列数 )
そうでないならば L(i) = 0
というようなことができそうだ
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(n)です
pseudocode（擬似コード）をかいてみますか。
S = 'leetcode'
D = ['leet', 'code']
L = [ [0] * len(S) for _ in range(len(S)) ]
for i in range(len(S)):
for j in range (i, len(S)):
if S[i:j] in D:
#ここむずかしい
L[i][j] = L[*][j- (j-i)]
else:
L[i][j] = 0 # かなー
L[i][j] = L[i-1][j] かもしれんほ
ちょっとむずかしいのはどうやって
伝搬するか、以下のように普通に0,1の埋めだけやっていくとこうなる
けど、カラムtの１は下へ伝搬していって問題ない。
L[i][j]の意味が文字列S[:j+1]を開始位置のバリエションiまで試してみた時に、文字が辞書に
存在したかどうかってことになる。
ので意味的にもOK
実装時はまったのは、やっぱり漸化式の更新の部分、コメントアウトしている感じでずっと書いていたがどこが間違いか全然わからずハマった。L関数のdefaultを1としていること、さらに、その戻り値と1のminを取ることに2つがあって初めてacceptedされる。前者はj-szが範囲外のときに効果があり、後者は、単純にj-sz時が0の場合、その後も全部0になるという基本てきな抑えなのだが、実際私はここの実装ができておらず苦労した。
dp[i][j] = max(min(1, L(i,j - sz, default=1)), L(i-1,j)) #dp[i][j] = max(L(i, j-sz, 1), L(i-1, j)) # これだと、j-szが, 0のパターンで間違い
あと工夫して、こんごの使いたいテクニックとして
dpもしくは配列へのアクセス関数を作ること
これがないと範囲内かどうかのif文がかなり邪魔になる
これがスッキリするのはとても大きい
dp = [ [0] * len(S) for _ in range(len(S)) ]
length = len(S)
def L(i, j, default=0):
if i < 0 or i >= length: return default
if j < 0 or j >= length: return default
return dp[i][j]
実際の実装はこちら
def wordBreak(S: str, D: List[str]) -> bool:
dp = [ [0] * len(S) for _ in range(len(S)) ]
length = len(S)
def L(i, j, default=0):
if i < 0 or i >= length: return default
if j < 0 or j >= length: return default
return dp[i][j]
for i in range(length):
for j in range (length):
if S[i:j+1] in D:
sz = j+1-i
dp[i][j] = max(min(1, L(i,j - sz, default=1)), L(i-1,j))
#dp[i][j] = max(L(i, j-sz, 1), L(i-1, j)) # これだと、j-szが, 0のパターンで間違い
else:
dp[i][j] = L(i-1,j)
if j == len(S)-1 and dp[i][j] == 1: return True
return True if dp[i][j] == 1 else False
実装後です。timespace analysis (時間とスペースの分析）は O(n**2)です
まとめ
・まぁ、つかえるぞ これDP問題を解くときの考え方マニュアル
・dpもしくは配列へのアクセス関数を作ること
以上です