LeetCode/NeetCode
[DP: LCS 최장공통수열 Longest Common Subsequence] 97. Interleaving String
hyunkookim
2024. 12. 30. 21:09
https://youtu.be/3Rw3p9LrgvE?si=Bs1PKA3LI4l3H4my
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
# 길이 조건 확인
if len(s1) + len(s2) != len(s3):
return False
dp = {}
def dfs(i, j):
# 종료 조건: s1과 s2를 모두 사용했을 때
if i == len(s1) and j == len(s2):
return True
# 이미 계산된 경우 캐시된 값 반환
if (i, j) in dp:
return dp[(i, j)]
# s1에서 문자를 가져오는 경우
if i < len(s1) and s1[i] == s3[i + j] and dfs(i + 1, j):
return True
# s2에서 문자를 가져오는 경우
if j < len(s2) and s2[j] == s3[i + j] and dfs(i, j + 1):
return True
# 위 조건을 만족하지 못하면 False
dp[(i, j)] = False
return False
return dfs(0, 0)
동작 원리
- DFS 호출:
- 현재 인덱스 i와 j에서 s3[i+j]가 s1[i] 또는 s2[j]와 일치하는지 확인하고, 각각의 경우에 대해 재귀적으로 호출합니다.
- 메모이제이션:
- (i, j) 상태에서 결과를 dp에 저장하여 동일한 상태에 대한 중복 계산을 방지합니다.
- 결과 반환:
- dfs(0, 0) 호출로 탐색을 시작하며, 종료 조건을 만족하면 True를 반환합니다.
GPT
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3): # 문자열 길이가 맞지 않으면 False
return False
# DP 테이블 생성
dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
dp[0][0] = True # 초기값: s1, s2, s3가 모두 빈 문자열인 경우
# 첫 번째 문자열(s1)의 부분 문자열을 사용하는 경우
for i in range(1, len(s1) + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
# 두 번째 문자열(s2)의 부분 문자열을 사용하는 경우
for j in range(1, len(s2) + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
# DP 테이블 채우기
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or \
(dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
return dp[len(s1)][len(s2)] # 최종 결과
코드 설명
- DP 테이블 정의:
- dp[i][j]: s1의 첫 ii개 문자와 s2의 첫 jj개 문자가 s3의 첫 i+ji + j개 문자를 구성할 수 있는지 여부를 저장합니다.
- 초기화:
- dp[0][0] = True: 모든 문자열이 빈 문자열인 경우 가능합니다.
- dp[i][0]: s1의 부분 문자열만으로 s3를 구성할 수 있는지 확인합니다.
- dp[0][j]: s2의 부분 문자열만으로 s3를 구성할 수 있는지 확인합니다.
- 점화식:
- dp[i][j] = True는 다음 두 조건 중 하나가 참인 경우:
- dp[i - 1][j]가 참이고, s1[i - 1] == s3[i + j - 1]
- dp[i][j - 1]가 참이고, s2[j - 1] == s3[i + j - 1]
- dp[i][j] = True는 다음 두 조건 중 하나가 참인 경우:
- 결과 반환:
- 최종적으로 dp[len(s1)][len(s2)]에 True가 저장되어 있으면, s3는 s1과 s2의 교차 문자열입니다.
97. Interleaving String은 **동적 계획법(DP)**을 활용해서 푸는 대표적인 2차원 DP 문제입니다. 아래에 처음부터 끝까지 상세하게 설명해드릴게요.
🔍 문제 요약
세 문자열 s1, s2, s3가 주어질 때,
s3가 s1과 s2를 순서를 유지하면서 섞어서 만든 문자열인지 확인하시오.
🧠 핵심 아이디어
- s1, s2의 문자를 하나씩 순서대로 선택해서 s3를 만들 수 있는지 확인
- 단, 순서는 지켜야 함 (s1, s2 내부의 문자 순서는 그대로)
✅ 조건 정리
- len(s1) + len(s2) == len(s3) 가 아니라면 False
- 한 글자씩 s1 또는 s2에서 뽑아 s3를 만들어야 함
📌 dp[i][j] 정의
| dp[i][j] | s1[0:i]와 s2[0:j]로 s3[0:i+j]를 만들 수 있는지 여부 (True/False) |
✅ 점화식
if s1[i-1] == s3[i+j-1]:
dp[i][j] |= dp[i-1][j]
if s2[j-1] == s3[i+j-1]:
dp[i][j] |= dp[i][j-1]- s3[i+j-1]를 만들기 위해 s1[i-1]을 쓸 수 있다면 → dp[i-1][j]에서 올 수 있음
- s2[j-1]을 쓸 수 있다면 → dp[i][j-1]에서 올 수 있음
✅ 전체 코드 + 상세 주석
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
M, N = len(s1), len(s2)
# 길이 안 맞으면 바로 False
if M + N != len(s3):
return False
# dp[i][j] = s1의 앞 i글자, s2의 앞 j글자로 s3의 앞 i+j글자 만들 수 있는지
dp = [[False] * (N + 1) for _ in range(M + 1)]
dp[0][0] = True # 공집합 + 공집합 → 공집합
# s1만 사용하는 경우 (s2는 비어 있음)
for i in range(1, M + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
# s2만 사용하는 경우 (s1은 비어 있음)
for j in range(1, N + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
# 두 문자열을 섞어 가며 dp 갱신
for i in range(1, M + 1):
for j in range(1, N + 1):
# s1의 문자가 s3와 일치 → s1에서 한 글자 쓴 경우
if s1[i - 1] == s3[i + j - 1]:
dp[i][j] |= dp[i - 1][j]
# s2의 문자가 s3와 일치 → s2에서 한 글자 쓴 경우
if s2[j - 1] == s3[i + j - 1]:
dp[i][j] |= dp[i][j - 1]
return dp[M][N]🧪 예제
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
sol = Solution()
print(sol.isInterleave(s1, s2, s3)) # 출력: True📌 시간 & 공간 복잡도
| 시간 | O(M × N) |
| 공간 | O(M × N) (→ O(N)으로 줄일 수도 있음) |
✅ 요약 정리
| 핵심 포인트 | 설명 |
| 길이 검사 | len(s1) + len(s2) == len(s3) 확인 필수 |
| dp[i][j] | s1[0:i], s2[0:j]로 s3[0:i+j]를 만들 수 있는지 |
| 초기화 | dp[0][0] = True부터 한 글자씩 누적 |