[js] Leetcode 1143. Longest Common Subsequence

문제

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

Longest Common Subsequence - LeetCode

- 두 문자열에서 공통으로 가장 긴 subsequence를 찾으시오. (비연속적이어도 됨)

ex). abcde, aced => ace

아이디어

생각하지 못함.

 

구현(풀이)

풀지 못함

 

남의 풀이

var longestCommonSubsequence = function(text1, text2) {
    let dp = new Array(text1.length+1).fill(null).map(
        ()=>new Array(text2.length+1).fill(0)
        );

    for (let i =1; i<text1.length+1; i++){
        for (let j =1; j< text2.length+1; j++){
            if (text1[i-1] === text2[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[text1.length][text2.length]
};

- 해당 이미지를 코드로 구현한 것이다.

- 배열을 순회하면서 알파벳을 비교한다. 알파벳은 두 개씩 비교하는 것이므로, 대각선으로 비교한다. 예를 들어서, a-a에서 오른쪽으로 한칸, 위로 한칸 가서 ab-ac를 비교하고 이전 값은 a-a의 1에서 더할 지 말 지를 결정한다.

- 초기값은 모두 0이고, 그림과 코드상으로는 첫번째 행과 열이 있는 게 편해서 모두 0을 만들어주고 1부터 순회를 시작한다.

- 일치하지 않는다면, 위와 왼쪽 선택지 중 큰 값을 따라간다. 해당 값에 이미 선행된 LCS이다. 그 값을 따라간다. 예를 들어서, xabccd-ac의 경우 이미 왼쪽값이 ac-ac로 결정이 되었고 ac-ad는 비교할 가치가 없는 값이다. 그렇다면 ac-ac를 따라가서 2가 되는 것이다.

구현은 쉬우나 아이디어가 어려워서 인상 깊은 문제였다.

참고문서

leetcode js 참고 코드 : https://leetcode.com/problems/longest-common-subsequence/solutions/1680148/javascript-dp-solution-with-written-intuition/

 

leetcode 풀이 설명 : https://leetcode.com/problems/longest-common-subsequence/solutions/348884/c-with-picture-o-nm/