1143. 最長共通部分列

2つの文字列 s1 と s2 が与えられたとき、これらの文字列の最長共通部分列の長さを返してください。共通部分列が存在しない場合は 0 を返します。

文字列の部分列とは、元の文字列から文字の相対的な順序を変更せずに一部の文字を削除（または削除しない）して形成される新しい文字列です。

• 例えば、"ace" は "abcde" の部分列ですが、"aec" は "abcde" の部分列ではありません。

2つの文字列の共通部分列とは、両方の文字列に共通して存在する部分列のことです。

例 1：

<strong>入力：</strong>s1 = "abcde", s2 = "ace" 
<strong>出力：</strong>3  
<strong>説明：</strong>最長共通部分列は "ace" で、その長さは 3 です。

例 2：

<strong>入力：</strong>s1 = "abc", s2 = "abc"
<strong>出力：</strong>3
<strong>説明：</strong>最長共通部分列は "abc" で、その長さは 3 です。

例 3：

<strong>入力：</strong>s1 = "abc", s2 = "def"
<strong>出力：</strong>0
<strong>説明：</strong>2つの文字列に共通部分列がないため、0 を返します。

制約：

• 1 <= s1.length, s2.length <= 1000
• s1 と s2 は小文字の英字のみで構成されます。

解法

1. 状態の定義：

   • 二次元配列 dp を定義します。ここで dp[i][j] は s1 の最初の i 文字と s2 の最初の j 文字の最長共通部分列の長さを表します。

2. 初期化：

   • dp[0][0] = 0 で初期化します。これは空の文字列2つの最長共通部分列の長さが0であることを意味します。

3. 状態遷移：

   • s1 と s2 の各文字を走査します。もし s1.charAt(i-1) == s2.charAt(j-1) であれば、dp[i][j] = dp[i-1][j-1] + 1 とします。これは、これらの文字が最長共通部分列の一部であることを意味します。
   • もし s1.charAt(i-1) != s2.charAt(j-1) であれば、dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) とします。これは、異なる文字の場合の最長共通部分列の長さを選択することを意味します。

4. 結果：

   • 最終的に dp[n][m] が s1 と s2 の最長共通部分列の長さとなります。

例

s1 = "abcde"、s2 = "ace" と仮定し、dp テーブルを埋めて最長共通部分列の長さを見つけます：

• dp[0][0] を 0 で初期化します。
• s1 と s2 の各文字を走査します：
  • i=1, j=1 の場合、s1.charAt(0)='a' と s2.charAt(0)='a' が同じなので、dp[1][1] = dp[0][0] + 1 = 1 となります。
  • i=2, j=2 の場合、s1.charAt(1)='b' と s2.charAt(1)='c' が異なるので、dp[2][2] = Math.max(dp[1][2], dp[2][1]) = 1 となります。
  • このようにして、dp テーブル全体を埋めます。

最終的に dp[5][3] の値は 3 となり、これは "abcde" と "ace" の最長共通部分列の長さです。

public int longestCommonSubsequence(String s1, String s2) {
    // 文字列s1の長さを取得
    int len1 = s1.length();
    // 文字列s2の長さを取得
    int len2 = s2.length();
    // 二次元配列dpを作成します。dp[i][j]はs1の最初のi文字とs2の最初のj文字の最長共通部分列の長さを表します
    int[][] dp = new int[len1 + 1][len2 + 1];
    // dp配列を初期化
    dp[0][0] = 0;
    // s1とs2の各文字を走査し、dp配列を埋めます
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            // s1のi番目の文字とs2のj番目の文字が同じ場合
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                // dp[i][j]はdp[i-1][j-1]に1を加えた値になります。これらの文字が最長共通部分列の一部であるためです
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // そうでなければ、dp[i-1][j]とdp[i][j-1]のうち大きい方を取ります。これは異なる文字の場合の最長共通部分列の長さを意味します
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // s1とs2の最長共通部分列の長さを返します。つまりdp[len1][len2]です
    return dp[len1][len2];
}