Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/description/

Longest Common Subsequence - LeetCode

 

두 문자열의 가장 긴 부분 문자열의 길이를 구하는 문제이다. 부분 문자열이란 말의 개념이 처음에는 혼돈이 와서 정답을 제출하면서 테스트 케이스들을 확인하고 진행하였다.

 

부분 문자열이란 두 전체 문자열을 이루는 문자들의 순서와 구성이 동일한 문자열을 말한다. 단 이때 전체 문자열에서 다른 문자가 있더라도 순서만 맞으면 된다.

 

1."ascne"
2."abdcet"

위의 두 문자가 있다면 최대 길이 부분 문자열은 "ace" 이다 ace 는 두 문자열을 이루는 문자에 순서대로 들어가며, 양쪽에 다 포함되기 때문이다.

 

문제를 이해하고 나서 풀이 방식이 떠오르지 않았지만 알고리즘 카테고리가 DP라는 것을 인지하고 나서는 풀이를 진행할 수 있었다. 만약 카테고리가 없었다면 혼자 풀기는 힘들었을 것 같다. 점화식의 아이디어는 두 문자열을 비교하는 것으로 시작한다.

1. 특정 인덱스의 두 문자열을 비교했을 때 두 문자열이 같다.
   ->두 문자열의 현재 인덱스 -1일 때의 최대 부분 문자열의 크기에서 1증가
2. 특정 인덱스의 두 문자열을 비교했을 때 두 문자열이 같다
   -> 두 문자열 인덱스 -1일 때 비교했을 때랑 최대 부분 문자열의 크기와 같음

인덱스 - 1 의 값을 처리해야 하므로 dp 배열의 크기를 +1 해주고 문자를 추출할 때는 -1 해서 문제를 해결해주었다. dp 배열의 마지막 행열 값이 문자열의 모든 문자를 확인한 값으로 최종 정답이 된다.

public class Solution {  
    public int longestCommonSubsequence(String text1, String text2) {  
  
        int text1Length = text1.length();  
        int text2Length = text2.length();  
  
        int[][] dp = new int[text1Length + 1][text2Length + 1];  
  
        for(int i = 1; i <= text1Length; i++){  
            char c1 = text1.charAt(i - 1);  
            for(int j = 1; j <= text2Length; j++){  
                char c2 = text2.charAt(j - 1);  
                if(c2 == c1){  
                    dp[i][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[text1Length][text2Length];  
    }  
}