[LeetCode] 97. Interleaving String

😎풀이

해당 문제는 문제 그대로 s1과 s2를 조합하여 s3를 만들 수 있는지를 판별하는 문제이다.

다만, 해당 문제를 백트레킹으로 풀이하려다 보니 Time limit이 발생하였다.

따라서, dp를 통해 메모이제이션 하며 풀이하였음

function isInterleave(s1: string, s2: string, s3: string): boolean {
    if (s1.length + s2.length !== s3.length) return false;
    
    // 메모이제이션을 위한 캐시
    const memo: boolean[][] = Array(s1.length + 1).fill(0)
        .map(() => Array(s2.length + 1).fill(undefined));
    
    function dp(i: number, j: number): boolean {
        // 기저 사례: 두 문자열을 모두 사용했을 때
        if (i === s1.length && j === s2.length) return true;
        
        // 이미 계산된 상태라면 캐시된 결과 반환
        if (memo[i][j] !== undefined) return memo[i][j];
        
        const k = i + j; // s3에서의 현재 위치
        
        // s1의 현재 문자를 사용할 수 있는 경우
        if (i < s1.length && s1[i] === s3[k] && dp(i + 1, j)) {
            return memo[i][j] = true;
        }
        
        // s2의 현재 문자를 사용할 수 있는 경우
        if (j < s2.length && s2[j] === s3[k] && dp(i, j + 1)) {
            return memo[i][j] = true;
        }
        
        return memo[i][j] = false;
    }
    
    return dp(0, 0);
}