iT邦幫忙

2

動態規劃經典題: 最長公共子序列(LCS)

最長公共子序列(LCS)

參考題目: 1143. Longest Common Subsequence
給你兩個字串,求它們的最長公共子序列的長度
例子:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

想法: 建一張表,令DP[i][j] 表示以text2[i]為結尾及text1[j]為結尾的最長子序列長度,
則我們有以下的關係式,
case1: 如果text1[j] == text2[i],則DP[i][j]= DP[i-1][j-1]+1
case2: 其它情形表示新加入「text1[j]」與「text2[i]」並不會用到,故DP[i][j] = max(DP[i-1][j], DP[i][j-1])

程式碼:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        
        int R = text2.size();
        int C = text1.size();
        vector<vector<int>> DP(R, vector<int>(C, 0));
        
        DP[0][0] = (text1[0] == text2[0]?1:0);
        
        for (int i = 1; i < R; i++){
            DP[i][0] = (text1[0] == text2[i]? 1: DP[i-1][0]);
        }

        for (int j = 1; j < C; j++){
            DP[0][j] = (text1[j] == text2[0]? 1: DP[0][j-1]);
        }

        for (int i = 1; i < R; i++)
            for (int j = 1; j < C; j++){
                if(text1[j] == text2[i]){
                    DP[i][j] = DP[i-1][j-1]+1;
                }
                else{
                    DP[i][j] = max(DP[i-1][j], DP[i][j-1]);
                }
            }
  
        return DP[R-1][C-1]; 
    }
};

延伸閱讀

如果需要省空間或更快的做法,參考演算法筆記- LCS


尚未有邦友留言

立即登入留言