LCS 알고리즘

 

❐ Description

---

[LeetCode#1143. Longest Common Subsequence]를 풀면서 학습한 LCS 알고리즘 정리

 

*참고 블로그 : [알고리즘] 그림으로 알아보는 LCS 알고리즘

 

 

 

 

❐ Longest Common Subsequence란?

---

우선 Longest Common Subsequence의 의미를 이해하자.

LCS란 두 문자열의 순서를 유지한 채 공통으로 존재하는 가장 긴 부분 수열을 찾는 것이다.

부분 수열이기 때문에, 주어진 문자열에서 순서만 유지하면 몇 개든 건너 뛰어도 된다.

Longest Common Substring이란?
주어진 문자열에서 순서를 유지한 채 공통으로 존재하는 연속된 문자를 찾는 것

 

 

 

 

 

❐ 점화식 이해하기

---

1. 두 문자가 동일한 경우

//text1[i - 1] == text2[k - 1]
memo[i][k] = memo[i - 1][k - 1] + 1

 

현재 비교하는 두 문자가 동일하다면, 바로 앞 문자까지 구한 LCS 값이 동일하기 때문에 1을 더해주기만 하면된다. 

Example1

 

 

2. 두 문자가 동일하지 않은 경우

//text1[i - 1] != text2[k - 1]
memo[i][k] = maxOf(memo[i -1][k], memo[i][k - 1]

Example2

위 예제의 표를 보면, `c != e` 가 성립하는 것을 확인할 수 있다. 따라서 현재 위치(memo[3,3]) 에서 LCS를

갱신해주기 위해서는 두 문자열 중 하나의 마지막 문자를 버리고 앞쪽 부분들끼리 비교해서 최댓값을 선택한다.

• 'ab' vs 'ace' (text1의 c를 버림)
• 'abc' vs 'ac' (text2의 e를 버림)

 

 

 

❐ 구현하기

---

 1. Kotlin

fun longestCommonSubsequence(text1: String, text2: String): Int {
    val maxRow = text1.length
    val maxCol = text2.length
    
    // Initialize 2D memoization array
    val memo = Array(maxRow + 1) { IntArray(maxCol + 1) }
    
    for (r in 1..maxRow) {
        for (c in 1..maxCol) {
            when {
                text1[r - 1] == text2[c - 1] -> memo[r][c] = memo[r - 1][c - 1] + 1
                else -> memo[r][c] = maxOf(memo[r - 1][c], memo[r][c - 1])
            }
        }
    } 
    
    return memo[maxRow][maxCol]
}

 

 

2. Java

public int longestCommonSubsequence(String text1, String text2) {
    int maxRow = text1.length();
    int maxCol = text2.length();

    // Initialize 2D memoization array
    int[][] memo = new int[maxRow + 1][maxCol + 1];

    for (int r = 1; r <= maxRow; r++) {
        for (int c = 1; c <= maxCol; c++) {
            if (text1.charAt(r - 1) == text2.charAt(c - 1)) {
                memo[r][c] = memo[r - 1][c - 1] + 1;
            } else {
                memo[r][c] = Math.max(memo[r - 1][c], memo[r][c - 1]);
            }
        }
    }

    return memo[maxRow][maxCol];
}

 

 

 

 

 

---