What is the best way to solve Interleaving String?

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

상위 150개 인터뷰중간

문자열 인터리브

'인터리빙 문자열' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

중간

문자열 s1, s2, s3이 주어지면 s3이 s1과 s2의 인터리빙으로 형성되는지 확인합니다.

두 문자열 s와 t의 인터리빙은 s = s1 + s2 + ... + sn, t = t1 + t2 + ... + tm, |n - m|과 같이 비어 있지 않은 하위 문자열로 분할되는 구성입니다. <= 1이고 인터리브된 문자열은 s1 + t1 + s2 + t2 + ... 또는 t1 + s1 + t2 + s2 + ...입니다.

isInterleave(s1: str, s2: str, s3: str) -> bool 함수를 작성하세요.

제약

•0 <= len(s1), len(s2) <= 100
•0 <= len(s3) <= 200
•s1, s2, and s3 consist of lowercase English letters

예

Example 1

Input

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Output

True

Explanation

aadbbcbcac can be formed by interleaving "aabcc" and "dbbca".

Example 2

Input

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

Output

False

Explanation

It is impossible to interleave s1 and s2 to obtain s3.

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 is_interleave_opt(s1, s2, s3):
    if len(s1) + len(s2) != len(s3): return False
    dp = [[False for j in range(len(s2) + 1)] for i in range(len(s1) + 1)]
    dp[len(s1)][len(s2)] = True
    for i in range(len(s1), -1, -1):
        for j in range(len(s2), -1, -1):
            if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]: dp[i][j] = True
            if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]: dp[i][j] = True
    return dp[0][0]

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

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

def is_interleave_brute(s1, s2, s3):
    if len(s1) + len(s2) != len(s3): return False
    def solve(i, j, k):
        if k == len(s3): return True
        res = False
        if i < len(s1) and s1[i] == s3[k]: res = res or solve(i + 1, j, k + 1)
        if j < len(s2) and s2[j] == s3[k]: res = res or solve(i, j + 1, k + 1)
        return res
    return solve(0, 0, 0)