1143. Longest Common Subsequence - Medium

前往題目

想法

• 毫無想法，看提示也不懂，幾乎沒做過2d DP

思路

這題要畫2d陣列才會清楚

1. 2d陣列，bottom up
2. 從右下開始，如果遇到相同的字，那就代表值在右下，因為text1和text2都前進一格，所以當前的值為1+右下的值
3. 如果沒有相同，那就看是右邊格子的數值大還是下面的

簡單來說就是top down是遇到相同的字就往右下，不是就往右和往下找，所以反過來推就是bottom up了

Code

NeetCode大大講得很清楚

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        final int M = text1.length(), N = text2.length();

        // dp[][] means LCS of text1[0 ... i] & text2[0 ... j]
        int[][] dp = new int[M + 1][N + 1];

        // Fill with zeros
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                dp[i][j] = 0;
            }
        }

        // Bottom up
        for (int i = M - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                // Same char
                if (text1.charAt(i) == text2.charAt(j)) {
                    // Current add previous
                    dp[i][j] = 1 + dp[i + 1][j + 1]; 
                } else {
                    // Take previous
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }

        return dp[0][0];
    }
}