What is the best way to solve Longest Common Subsequence?

The optimized O(n) approach using 2D DP patterns is generally preferred.

상위 150개 인터뷰중간

가장 긴 공통 부분 수열

'최장 공통 부분 수열' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

중간

두 개의 문자열 text1과 text2가 주어지면 가장 긴 공통 부분 수열의 길이를 반환합니다. 공통 부분 수열이 없으면 0을 반환합니다.

문자열의 하위 시퀀스는 나머지 문자의 상대적 순서를 변경하지 않고 일부 문자가 삭제된(없음일 수 있음) 원래 문자열에서 생성된 새 문자열입니다. (예를 들어 "ace"는 "abcde"의 하위 시퀀스입니다.)

longestCommonSubsequence(text1: str, text2: str) -> int 함수를 작성하세요.

제약

•1 <= len(text1), len(text2) <= 1000
•text1 and text2 consist of only lowercase English characters

예

Example 1

Input

text1 = "abcde", text2 = "ace"

Output

Explanation

The longest common subsequence is "ace" and its length is 3.

Example 2

Input

text1 = "abc", text2 = "abc"

Output

Explanation

The longest common subsequence is "abc" and its length is 3.

Example 3

Input

text1 = "abc", text2 = "def"

Output

Explanation

There is no common subsequence, so the result is 0.

Need a Hint?

세트나 힙과 같은 2D DP 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

2D DP 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def lcs_opt(text1, text2):
    dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]
    for i in range(len(text1) - 1, -1, -1):
        for j in range(len(text2) - 1, -1, -1):
            if text1[i] == text2[j]: dp[i][j] = 1 + dp[i + 1][j + 1]
            else: dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
    return dp[0][0]

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def lcs_brute(text1, text2):
    def solve(i, j):
        if i == len(text1) or j == len(text2): return 0
        if text1[i] == text2[j]: return 1 + solve(i + 1, j + 1)
        return max(solve(i + 1, j), solve(i, j + 1))
    return solve(0, 0)