LeetCode #1143 Longest Common Subsequence

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #1143 Longest Common Subsequence

문제 풀이

text1, text2로 두 개의 스트링이 주어진다. 이 스트링들이 서로 갖는 최대의 substring 길이를 리턴하면 된다. 전형적인 dp문제로 꽤 좋은 문제라 생각한다.

• 좌표 기준으로 이전까지의 substring 최댓값을 관리해야 함
• [text1의 길이 + 1][text2의 길이 + 1]만큼의 2차원 배열 생성
  • 탐색 좌표 기준 이전 좌표값까지의 substring 길이를 참조해야 하므로 1좌표부터 입력
• 이중 for문으로 탐색, 1부터 text1까지, 1부터 text2까지 탐색
• dp배열 [i][j]는 i - 1번째 좌표와 j - 1번째 좌표의 탐색 결과를 담는다고 간주
• text1[i - 1] == text2[j - 1]이면 substring 길이가 1 증가했다는 의미로 dp[i - 1][j - 1] + 1을 입력
• 만약 같지 않다면 1을 더할 여지가 없으므로 max(dp[i - 1][j], dp[i][j - 1])을 입력

python 코드 - 1

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        text1Len, text2Len = len(text1), len(text2)
        dp = [[0 for _ in range(text2Len + 1)] for _ in range(text1Len + 1)]
        for i in range(1, text1Len + 1):
            for j in range(1, text2Len + 1):
                if text1Len[i - 1] == text2Len[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[text1Len][text2Len]

python 코드 - 2 (공간복잡도 개선)

어차피 좌표기준으로 탐색하고 1부터 끝까지 진행한다는 점에서 누적합의 개념을 생각해볼 수 있다. 그렇다면 text1, text2 중 하나는 차원을 2로 줄여서 홀-짝으로 구분해볼 수 있겠다.

만약 text1 탐색 매개변수 i에 대해 짝수라고 가정하자.

• 검사하는 좌표의 글자가 같고 i가 짝수라면 [홀수][j - 1]의 값에서 + 1 한 결과를 입력
• 글자가 같지 않다면 max([짝수][j - 1], [홀수][j])를 입력

결국 리턴해야 하는 값은 [text1Len % 2][text2Len]이므로 리턴될 좌표에 최종 탐색값이 입력되게끔만 보장해주면 된다.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        text1Len, text2Len = len(text1), len(text2)
        dp = [[0 for _ in range(text2Len + 1)] for _ in range(2)]
        for i in range(1, text1Len):
            for j in range(1, text2Len):
                if text1[i - 1] == text2[j - 1]:
                    dp[i % 2][j] = 1 + dp[1 - i % 2][j - 1]
                else:
                    dp[i % 2][j] = max(dp[1 - i % 2][j], dp[i % 2][j - 1])
        return dp[text1Len % 2][text2Len]