1143. Longest Common Subsequence

• 두 문자열 text1, text2의 가장 긴 공통 부분 배열의 길이를 구한다.

• 두 문자열을 동시에 탐색하면서 특정 위치 i, j의 문자를 부분 배열에 포함 시킨다. 이 때 양쪽의 문자열이 같은지 확인한다.
• 만약 현재 위치의 문자열이 같다면 양쪽의 위치를 똑같이 1 씩 증가 시킨다. 공통되는 부분 배열의 길이는 마찬가지로 1 증가한다.
• 만약 현재 위치의 문자열이 같지 않다면 첫번째 문자열의 위치 i 또는 두번째 문자열의 위치 j를 1 증가시킨다. 두 경우 중에 더 긴 공통 부분 배열을 가진 것을 최종 값으로 한다.
• 양쪽의 문자를 탐색하는 위치 (i, j) 별로 공통 부분 배열의 최대 길이는 항상 동일하게 계산되므로 memoization을 활용한다.

• 위에서 설명한 방식을 그대로 구현하면 아래와 같다. 통과는 되기는 하는데 실행 속도가 느리다 (61 ms).

class Solution {
    int traverse(String text1, String text2, int[][] dp, int i, int j) {
        if (i >= text1.length() || j >= text2.length()) {
            return 0;
        }
        if (dp[i][j] != -1) return dp[i][j];
        boolean isSameChar = text1.charAt(i) == text2.charAt(j);
        return dp[i][j] = Math.max(
            traverse(text1, text2, dp, i + 1, j + 1) + (isSameChar? 1 : 0),
            Math.max(
                traverse(text1, text2, dp, i + 1, j),
                traverse(text1, text2, dp, i, j + 1)
            )
        );
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()][text2.length()];
        for (int[] sub : dp) {
            Arrays.fill(sub, -1);
        }
        return traverse(text1, text2, dp, 0, 0);
    }
}

• 같은 로직을 for loop로 구현할 수 있다.
• 편의상 memoization 배열 dp의 크기를 1 더 크게 잡는다.
• 현재 index 값 (i, j)을 기준으로 이전 위치 (i - 1, j - 1)의 값을 비교한다.
• 만약 0부터 시작하는 index를 사용하게 되면 i, j 값이 0보다 큰지 매번 확인해야 되는 번거로움이 있다.
• 비교한 양쪽 문자가 동일하면 양쪽 모두 index를 1씩 증가 시키는 것이므로 이전 index의 결과값 dp[i - 1][j - 1]에 1을 더한 것이 현재 index의 결과값 dp[i][j]이 된다.
• 비교한 양쪽 문자가 동일하지 않으면 어느 한쪽의 index를 1 증가시키는 것이므로 각각의 이전 index의 결과값들 dp[i - 1][j], dp[i][j - 1] 중 큰 값을 현재 index의 결과 dp[i][j]로 한다.
• 최종 결과 값은 양쪽 모두의 마지막 index 위치의 결과값dp[m][n]으로 한다.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++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 - 1][j], dp[i][j - 1]);
                    
                }
            }
        }
        return dp[m][n];
    }
}