[LeetCode] 1143. 가장 긴 공통 부분 수열

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

두 개의 문자열이 주어지면 텍스트 1 그리고 텍스트2, 반품 가장 긴 길이 공통부분수열. 없는 경우 공통부분수열, 반품 0.

에이 후속 문자열은 나머지 문자의 상대적 순서를 변경하지 않고 일부 문자가 삭제된(없음일 수 없음) 원래 문자열에서 생성된 새 문자열입니다.

예를 들어, "에이스" 의 후속이다 "abcde".

에이 공통부분수열 두 문자열의 는 두 문자열 모두에 공통인 하위 시퀀스입니다.

예시 1:

입력: text1 = "abcde", text2 = "에이스" 
산출: 3  
설명: 가장 긴 공통 부분 수열은 "ace"이고 길이는 3입니다.

예 2:

입력: text1 = "abc", text2 = "abc"
산출: 3
설명: 가장 긴 공통 부분 수열은 "abc"이고 길이는 3입니다.

예시 3:

입력: text1 = "abc", text2 = "def"
산출: 0
설명: 그러한 공통 부분 수열이 없으므로 결과는 0입니다.

제약:

1 <= 텍스트1.길이, 텍스트2.길이 <= 1000
텍스트 1 그리고 텍스트2 영어 소문자로만 구성됩니다.

파이썬

				
					# 시간 복잡도: O(n*m) # 공간 복잡도: O(n*m) 클래스 해결 방법: def maximumCommonSubsequence(self, text1: str, text2: str) -> int: dpGrid = [[0] * (len( text2) + 1) for _ in range(len(text1)+1)] for col in reversed(range(len(text2))): for row in reversed(range(len(text1))): if text2[col ] == text1[row]: dpGrid[row][col] = 1 + dpGrid[row+1][col+1] else: dpGrid[row][col] = max( dpGrid[row+1][col] , dpGrid[row][col+1]) return dpGrid[0][0] text1 = "abcde" text2 = "ace" print(Solution().longestCommonSubsequence(text1, text2))

중간

파이썬

관련 기사