[LeetCode#1143] Longest Common Subsequence

 

❐ Description

---

1. Requests

• 주어진 두 문자열의 겹치는 subsequence 중 가장 긴 문자열의 길이를 반환하라.
• 겹치는 부분이 없다면 0을 반환하라.
•  두 문자열의 순서를 유지한 채 공통으로 존재하는 가장 긴 부분 수열을 찾는 것

 

2. Constrains

• `1 <= 주어진 문자열의 길이 <= 10³`
• 제약 조건에 의하면 시간복잡도는 최대 O(n²)까지는 괜찮다.

 

 

 

 

 

❐ Approach  1 - 2D memoization (Bottom - Up)

---

class KtSolutionV1 {
    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]
    }
}

1. 테이블 형식의 2차원 배열을 생성 후 0으로 초기화 해준다.
   • 최대 row, 최대 col
2. 외부 for문은 row를 순회하고, 내부 for문은 col을 순회한다.
   • 순외하는 순서는 바뀌어도 됨
3. 문자를 비교한다.
   • 비교하는 문자가 동일한 경우
   • 비교하는 문자가 동일하지 않은 경우
4. 테이블의 마지막 row, col의 값을 반환한다.

 

 

 

 

 

❐ Approach 2 - 1D memoization (Bottom-Up) 

---

아래의 접근 방식은 2D 테이블 대신 1D 배열을 사용하여 공간 복잡성을 줄일 수 있다.

class KtSolutionV2 {
    fun longestCommonSubsequence(text1: String, text2: String): Int {
        val x = text1.length
        val y = text2.length

        val memo = IntArray(y + 1)

        for (i in 1..x) {
            // 대각선
            var prev = 0
            for (k in 1..y) {
                // 같은 행 윗 열
                val temp = memo[k]
                if (text1[i - 1] == text2[k - 1]) {
                    memo[k] = 1 + prev
                } else {
                    // memo[k - 1] : 같은 열 왼쪽 행
                    memo[k] = maxOf(memo[k], memo[k - 1])
                }
                prev = temp
            }
        }
        return memo[y]
    }
}

• prev : 2D에서 memo[i-1][k-1]에 대응
• temp : 2D에서 memo[i-1][k]에 대응

 

 

 

 

 

❐ [Advanced] Approach 3 - 1D memoization (Bottom-Up) 

---

아래의 접근 방식은 2D 테이블 대신 1D 배열을 사용하여 공간 복잡성을 줄일 수 있다.

class KtSolutionV3 {
    fun longestCommonSubsequence(text1: String, text2: String): Int {

        val memo = IntArray(text1.length)

        var maxLength = 0
        for (c in text2.toCharArray()) {
            var currentLength = 0
            for (k in memo.indices) {

                // memo[k] = dp[i-1][k] : 테이블로 치면 같은 열의 윗쪽 행
                // currentLength = dp[i][k-1] : 테이블로 치면 같은 행의 왼쪽 열
                if (currentLength < memo[k]) {
                    currentLength = memo[k]
                }

                // currentLength = dp[i-1][k-1]
                else if (text1[k] == c) {
                    memo[k] = currentLength + 1
                    maxLength = maxOf(maxLength, memo[k])
                }
            }
        }
        return maxLength
    }
}

Approach2와는 달리, `currentLength`변수 하나로 아래의 경우를 모두 대응할 수 있다.

 

1. 두 개의 문자가 동일하지 않은 경우

• 여기서 currentLength는 2D의 memo[i][k-1]에 대응 

 

2. 두 개의 문자가 동일한 경우

• 여기서 currentLength는 2D의 dp[i-1][k-1]에 대응

 

text1 = "abcde", text2 = "ace"

1. text2[0] = 'a'
memo = [1, 0, 0, 0, 0] | currentLength = 0 | maxLength = 0
memo = [0, 0, 0, 0, 0] | currentLength = 0 | maxLength = 0
memo = [0, 0, 0, 0, 0] | currentLength = 0 | maxLength = 0
memo = [0, 0, 0, 0, 0] | currentLength = 0 | maxLength = 0
memo = [0, 0, 0, 0, 0] | currentLength = 0 | maxLength = 0


2. text2[1] = 'c'
memo = [1, 0, 0, 0, 0] | currentLength = 1 | maxLength = 1
memo = [1, 0, 2, 0, 0] | currentLength = 1 | maxLength = 2
memo = [1, 0, 2, 0, 0] | currentLength = 1 | maxLength = 2
memo = [1, 0, 2, 0, 0] | currentLength = 1 | maxLength = 2
memo = [1, 0, 2, 0, 0] | currentLength = 1 | maxLength = 2


3. text2[1] = 'e'
memo = [1, 0, 2, 0, 0] | currentLength = 1 | maxLength = 2
memo = [1, 0, 2, 0, 0] | currentLength = 1 | maxLength = 2
memo = [1, 0, 2, 0, 0] | currentLength = 2 | maxLength = 2
memo = [1, 0, 2, 0, 0] | currentLength = 2 | maxLength = 2
memo = [1, 0, 2, 0, 3] | currentLength = 2 | maxLength = 3

 

 

 

 

 

---