こんにちは
今回の学びは
・悩んでも、何をやっているのか分からなくなったら、一回俯瞰してハイレベルで物事をみようとしてみてください。
・サブケースを考える時は常に最も簡単なケース（入力が最小）から考える
問題はLCS Longest Common Subsequence 最大共通部分列 です。
有名な問題なので、ちゃんと理解していきましょう
まずは入出力をしっかりおさえましょう。
入力は文字列が二つ。求めたいのは最大共通部分列の長さなのでintを返します。
文字列がnull だったら？共通部分はないので0を返そう
実際の例をみた方が早い。abcdeとaceって aceは順序的にabcdeに含まれているから答えは3って感じ
abcとabcは全部一緒なので3。最後、abc, defは１文字も合ってないので0。を返す要領です
samples = [
("abcde", "ace", 3),
("abc", "abc", 3),
("abc", "def", 0),
]
もうちょっとサンプルを足したいですね。
telephone, leo なんかは最初の例と変わらないけど、実際の言葉を使っていること。
beebees, meeek これはeeeの被り方が２パターンあってややこしそう。
とこれらのサンプルで問題を進めていこうと思います
まずは総当たりで考えましょう
総当たりを考えるときは、実行速度よりもより完結なコードが書けるようなものすると、以外にそのあとの最適化（例えばdpとか再帰)とかに持って言いやすいという経験則があります
abcde と ace を考えた時
abcdeという文字で作れる文字の組み合わせは aを使う使わない、bを使う使わない, cを使う使わない, dを使う使わない, eを使う使わない,
とう感じで2**5とうことになります。同様にaceも方も2**3なので 文字列1の長さをnと文字列2の長さをmとした時
O( 2 **(n+m) )ということになりtimespace analysisとそれぞれの許容入力サイズでまとめたように２８文字くらいまでしか
現実的な速度で応答できなくて、これではつかないことがわかります。
次に、漸化式にできないかなー 考えます
＝＝＝＝★★★★★★★ あとでわかったことですが、以下 間違っていた迷走したときのメモですので、興味ない方は次の★★★マークまで読みとばしてください ＝＝＝＝
abcde, ace
ここで登場しないといけない変数は文字列1に文字列2に答えである最大共通部分列数、
文字列1が小さいパターンと文字列2が小さいパターンを考えてみる
abc, aceの場合、最大共通部分列数(LCS)はacの2だね
もっと短く
ab, acの場合、最大共通部分列数(LCS)はaの1だね
もっと短く!
a, aの場合、最大共通部分列数(LCS)はaの1だね
もっと短く!!
a, "" の場合、文字列２を全部減らしてやって空文字にしてやったぜ！最大共通部分列数(LCS)は一個もないのでの0だね
これを逆再生で
a , "" => 0 じゃあ
a, a => 1 じゃあ
ab, a => 1 じゃあ
abc, a => 1 じゃあ
abc, ac => 2 じゃあ
ってな風にできそうで、抽象的に考えれば文字を一個増やすごとにポテンシャル的には最大共通部分列が +1されるか、されないかのどちらかだ。
そうすると
文字列1のi番目までの文字列と
文字列2のj番目までの文字列の 最大共通部分列数を求める場合
L(i, j) = LSC(i-1, j) + 1 それか
LSC (i , j-1) + 1 になりそうだCS
というような、漸化式が作れそうだ
文字列1をabcとして 文字列2を a としたとき、次のアクションで 文字列2 をインクリさせて acにしたとき
を考えてみよう。
abc ----> abc a ----> ac 1 ----> 2
最初に計算していたとして、abc, aの 最大共通部分列数は1でした。
文字列2にcを追加したのでcが文字列1の最終文字と一緒かどうか、だけを確認します
ab と a は 1 。 ab と ac は １。 abc と ac は 2。
ふーん
ここはエクセルの出番ではないでしょうか
こんな風に考えました。私はこの問題以前にやっているので、こうすべき等のはわかっているものの
うまく言葉で理解できていません。実際エクセルに説明していっても、解答がない状態からはたどり着けるとは思いません。
とりあえず、説明はこんな感じ >>1 っと書いているのは左の状態でのLCSは1 ということを表しています
abcとacを考えるとき、太文字が今追加された文字だとすると
１、なぜ、対文字列の最後の文字と比較するのか？
２、なぜ、前の状態を考慮しないといけないのか？
３、気にしないといけないのは２だけか？
それぞれの答えは
１、なぜ、対文字列の最後の文字と比較するのか？ ＝＞一個文字列が増えたわけで、もしそれが一緒なら共通部分+1でしょ！でもそれだけだと、aacとccのパターンで通用しないよね。だから追加される前の状態aacとcだった頃が気にならない！？
２、なぜ、前の状態を考慮しないといけないのか？ ＝＞ 気になるよね！aacとcって共通部分列はすでにcやん。aacにccが入ってきたら
先輩c(緑)のはどう思う？新参者c (青)がわがもの顔で入ってきて、俺のおかげで+1だと！？いやいや。それは俺の功績やし、お前意味ないぞ！と。 ということは、新参者c (青)からしたらもしお前、c(緑)がおらんかったら時の状態やったらどうなってたんや、って確かめたいようね。ということでaacと""の状態のLCSが>>0だったことを確認する、だから >>0、俺c (青)が入って >>1になると安心する。一方、同様に対文字列のほうも同じことをしてみよう。ccがいたとしてaccではなくacだったらば。ac, cc >>1だった状態ですよ。これを調べる意味が見えてこない。aa, ccの状態を見ることになんの意味があるのかaacと"" >> 0, aa, c >> 0
ががが、完全に迷走しだした。。しばしお付き合い。
aac, c ==の一個前の状態って==> aac, "" >> 0, aa, c >> 0
aac, cc >> 1
aac, cccを考える
acc, ccc , c == c ,
acc, cc >> 2 , max (acc, c >> 1, ac, cc >> 1 ) + 1 so >> 2
aacc, cccを考える c == c だから +1
前の状態２パターンを考える。aac, ccc >> 1 , max(aa, ccc >> 0 , aac, cc >> 1) +1 so >> 2
３、気にしないといけないのは２だけか？
。。。あかん、
ハマって、何もわからんくなった。
＝＝＝＝ ここまでは 微妙に真を捉えておらず、結構時間ロスしました ★★★★★★★ ＝＝＝＝
（考えること自体決して無駄ではないのですが、最初の漸化式の検討が違うとこれほどまでに時間を食うものかと恐れ入りました。）
。。。
うわぁーーー
全部、検討違いでした。
昔の記憶を頼りにdp表作ってよれらしい動きになるように、いじって見る方が早かった。
しかし、
１、出てきたアルゴリズムは、最後の文字列が同じなら、その文字は省いたバージョンでの最大共通部分列数に +1
文字列が同じパターンは以下のように
２、そうでない場合は、追加文字列の一個前の文字をそれぞれ文字列１、文字列２からとった場合のLCSのうち最大のもの。
文字列が違う場合は、２のパターンなので、以下のようにで更新
ちょっと考えても、この考えてに至れない！！！
最後の文字列が同じなら、最後の文字列を両者から抜いた場合のLCS に +1 したもの
というこん一行が出てこなかった。
これぞdpの難しさよ。。。。
つまり。
正解の漸化式Lは
L[i][j] = L[i-1][j-1] + 1 when text1[j] == text2[i] otherwise L[i][j] = max(L[i-1][j], L[i][j-1] )
が正解の漸化式の建て方だったのですが
最初に満をじして、こう立てかけました。
それを正当化しようと、ドツボにハマりました。
間違いの漸化式Lは
L(i, j) = L(i-1, j) + 1 それか LSC (i , j-1) + 1 になりそうだCS
で、この中途半端な出だしを
最後まで修正できずに終わりました。。。
迷走していたときのメモを見直してみると、サンプルケースの5文字とかだったら
3,4文字くらいをつかってサブケースをかんがえています。
そうではなく、もっともかんたんなケース１文字もしくは０文字からかんがえていったほうが
いいかもしれない。
なので次回への教訓としては
サブケースを考える時は常に最も簡単なケース（入力が最小）から考える
ということを実践してみたい
まぁ、最低限、記憶を頼りに実装して提出パスでできましたので
理屈は抜きにせよ、表を使って何が正しそうか、という判断は間違っていませんでした。
時にはこういうヒューリスティックなアプローチで持って正解をだし
あとで正解の理由を考えるのも、ダメではありません。
ただ、最初に理屈がわかって、ちゃんと言葉にして、実装を進める方が
より再現性もあるし、プログラマーとして評価できるということ。
もっと問題をといてパターンになれる、ことを続けていきたいと思います。
それで振り返ってこの問題もすんなり解けるようになれるかが大事なことだと思います
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は dp表なのでO (n)
pseudocode（擬似コード）をかいてみますか。
答えが、わかってしまった今なら。
lcs = [ [0] * len(text1) for _ in range(len(text2)) ]
for i in range(len(text2)):
for j in range(len(text1)):
もし文字列同じなら LCS[この文字抜いたバージョン] + 1
それ以外なら、この文字以外をそれぞれ引いたバージョンのLCSの大きい方
最後に、ちょっとただのメモ書きになりますが、何をしれべようとしていたのか
自分で自己解析しようとしたメモです
最大共通文字列を変数で更新していくのも有りだとは思いますが、[h, t]の状態でtが再び同じでもダメーとかは言えるかもしれない。
ただしさらなる条件わけが出てくるし複雑。追えないよ。
実際の実装はこちら
import logging
#logging.basicConfig(level=logging.INFO, format="%(message)s")
logging.basicConfig(level=logging.DEBUG, format="%(message)s")
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0] * len(text1) for _ in range(len(text2))]
for row in dp:
logging.debug(row)
for i in range(len(text2)):
for j in range(len(text1)):
if text1[j] == text2[i]:
if i-1 >=0 and j-1 >=0:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = 1
else:
dp[i][j] = max(
0 if i == 0 else dp[i-1][j],
0 if j == 0 else dp[i][j-1]
)
return dp[i][j]
samples = [
("abcde", "ace", 3),
("abc", "abc", 3),
("abc", "def", 0),
]
for text1, text2, expected in samples:
print("-"*20)
ans = Solution().longestCommonSubsequence(text1, text2)
assert ans == expected, "(%s, %s) => %s but %s was expected" % (text1, text2, ans, expected)
print("(%s, %s) = %s as expected!" % (text1, text2, ans))
実装後です。timespace analysis (時間とスペースの分析）は O(n)でスペースも O(n) です
まとめ
敗因は、言葉にしきれなかったこと。具体例を追いすぎて、俯瞰した柔軟な思考ができてなかったこと。
・悩んでも、何をやっているのか分からなくなったら、一回俯瞰してハイレベルで物事をみようとしてみてください。
・サブケースを考える時は常に最も簡単なケース（入力が最小）から考える
以上です