LeetCode: Longest Common Subsequenceを解く

問題

LeetCode 30-Day LeetCoding Challenge 26日目です。
ここまで一日も欠かさずやってますが、急激に飽きてきたので、解きがてら適当にブログにまとめてみることにしました。

leetcode.com

2つの最長共通文字列を見つけて、その数を返す問題です。 ポイントは最長連続文字列ではなく最長共通文字列な点です。

以下に具体的な違いを例として示します。

text1 = "acde", text2 = "ace" 
最長連続文字列: ac
最長共通文字列: ace

解き方

動的計画法を使います。

詳しくは以下の動画を参考にしましょう。（クソ雑） www.youtube.com BackToBack SWEは数あるLeetCode解説動画の中でもわかりやすくて超絶お勧め。 英語が多少わからなくてもホワイドボードの説明が超絶わかりやすい。

詳細は動画を見てくださいで済ませますが、自分が理解のために書いた図を雑にはります。

提出したコード

動画のアルゴリズムをそのままコードにしただけ。 ポイントとしては文字列と動的計画法の保存用テーブルが1ズレるため、実際にfor文を回すときには+1か-1をして調整が必要。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1, n2 = len(text1), len(text2)
        dp = [[0 for _ in range(n2+1)] for _ in range(n1+1)]
        
        for i in range(n1):
            for j in range(n2):
                if text1[i] == text2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
                    
        return dp[-1][-1]

無事にAcceptedになりました。