Leetcode題解 Python & C#：四月挑戰DAY26 Longest Common Subsequence

給兩個字串，請回傳兩字串有幾個相同的部分？匹配的位置可以不用相鄰，但相對位置要一致。

這不是一般的字串匹配問題，因為匹配的部分可以不相鄰。

換個思維，要如何做到不相鄰的配對？

首先看兩者的[0]位，如果相同，則兩者往右尋找。
若不，則 text2 往下一位 [j+1] 匹配,，因此，對應 text2 的索引 j 的意思是 j 之前的匹配數目。
如果沒有匹配對，那 [j] 就等於上一位 [j-1] 的數目。
此外，因為可以不相鄰，所以 text1[i] text2[j] 沒有匹配到的話，[i][j]也可以從[i-1][j] 得到匹配數目。
於是沒有匹配的話 =>  [i][j] = max([i-1][j], [i][j-1])

這是正序的方法，若看 Hint ，我第一個寫成反序的遞迴函數，其實道理都相同。


如果有匹配到，數目一定是 +1 ，那是什麼位置的數目 +1 ？
[i-1][j-1]，這邏輯就像一般的字符匹配那般。

流程

Python

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1, l2 = len(text1), len(text2)
        cur = [0] * (l2+1)
        for i in range(l1):
            cur, pre = [0]*(l2+1), cur
            for j in range(l2):
                if text1[i] == text2[j]:
                    cur[j] = pre[j-1] + 1
                else:
                    cur[j] = max(cur[j-1], pre[j])
        return cur[-1]

C#

public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        var cur = new int[text2.Length+1];
        Array.Fill(cur, 0);
        for(int i = 0; i < text1.Length; i++)
        {
            var pre = cur;
            cur = new int[text2.Length+1];
            Array.Fill(cur, 0);
            for(int j = 0; j < text2.Length; j++)
            {
                if(text1[i] == text2[j])
                {
                    cur[j+1] = pre[j] + 1;
                }
                else
                {
                    cur[j+1] = (cur[j] > pre[j+1])? cur[j]: pre[j+1];
                }
            }
        }
        return cur[text2.Length];
    }
}