1143. Longest Common Subsequence

Refer to labulado's one:

https://github.com/jiajunhua/labuladong-fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.md

DFS

關鍵 ->

lcs 當有相同的字時, dp(i-1,j-1) + 1

不相同時 可能是 max(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)), 因為取最大 所以 dp(i-1, j-1) 效果不好 可以忽略

一路從尾巴 倒推回頭(-1 是終止條件)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return dp(text1, text2, text1.length()-1, text2.length()-1);
    }
    private int dp(String text1, String text2, int i, int j) {
        if (i == -1 || j == -1) {
            return 0;
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            return dp(text1, text2, i-1, j-1) + 1;
        } else {
            return Math.max(dp(text1, text2, i-1, j), dp(text1, text2, i, j-1));
        }
    }
}

Memo + DFS

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        return dp(text1, text2, m-1, n-1, new Integer[m][n]);
    }
    private int dp(String text1, String text2, int i, int j, Integer[][] memo) {
        if (i == -1 || j == -1) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            return memo[i][j] = dp(text1, text2, i-1, j-1, memo) + 1;
        } else {
            return memo[i][j] = Math.max(dp(text1, text2, i-1, j, memo), dp(text1, text2, i, j-1, memo));
        }
    }
}

DFS+memo, from 0, 0

    private int LCS(String word1, String word2) {
        return dp(word1, word2, 0, 0, new Integer[word1.length()+1][word2.length()+1]);
    }
    private int dp(String word1, String word2, int i, int j, Integer[][] memo) {
        if (i < word1.length() && j < word2.length()) {
            if (i == word1.length() && j == word2.length()) {
                return 0;
            }
            if (memo[i][j] != null) {
                return memo[i][j];
            }
            if ( word1.charAt(i) == word2.charAt(j)) {
                return memo[i][j] = dp(word1, word2, i+1, j+1, memo)+1;
            } else {
                return memo[i][j] = Math.max( 
                    dp(word1, word2, i, j+1, memo), 
                    dp(word1, word2, i+1, j, memo)
                );
            }
        }
        return 0;
    }
    private int max(int i, int j, int k) {
        return Math.max(Math.max(i, j),k);
    }

所以 dp table 存的就會是

the length of longest common subsequence of A[i] and B[j]

time: O(mn)

space: O(mn)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int dp[][] = new int[m+1][n+1];
        
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

new way

if we add in string , more "" in the front, the index become normal i, j

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        text1 = "#" + text1;
        text2 = "#" + text2;
        
        int dp[][] = new int[m+1][n+1];
        
        dp[0][0] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}

compressed to 1d

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        text1 = "#" + text1;
        text2 = "#" + text2;
        
        int dp[] = new int[n+1];
        
        dp[0] = 0;
        
        for (int i = 1; i <= m; i++) {
            int pre = 0;
            for (int j = 1; j <= n; j++) {
                int cur = dp[j];
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[j] = pre + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j-1]);
                }
                pre = cur;
            }
        }
        return dp[n];
    }
}

buttom up

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