[LeetCode] 97. Interleaving String

https://leetcode.com/problems/interleaving-string/description/

Interleaving String - LeetCode

문제 유형 : 문자열 처리 / 동적 계획법

문제 난이도 : Medium

 

문제

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

 

문자열 s1, s2, s3이 주어진다. s3이 s1과 s2의 부분문자열을 한 번씩 써서 이루어져있는지 확인하시오.

 

풀이

dp 테이블을 2차원으로 만든다. dp[i][j]는 s3의 인덱스 0부터 s3[i+k]까지의 부분 문자열을 만들 수 있는지에 대한 참 / 거짓 값이다.

dp[i-1][j]의 값을 만들 수 있는지 확인하고, s1[i-1]과 s3[i+k-1]이 동일한지를 검사한 후 가능하다면, 생성 가능한 dp[i][j] 값을 설정한다.

반대로, dp[i][j-1]의 값을 만들 수 있는지 확인하고, s2[j-1]과 s3[i+k-1]이 동일한지를 검사한 후 가능하다면, 생성 가능한 dp[i][j] 값을 설정한다.

 

dp[len1][len2]에는 최종적으로 완성할 수 있는지에 대한 여부가 있다.

 

코드

C++

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.size();
        int len2 = s2.size();
        int len3 = s3.size();

        if(len1 + len2 != len3) return false;

        vector<vector<bool>> dp (len1 + 1, vector<bool>(len2 + 1, false));
        dp[0][0] = true;

        for(int i = 0; i <= len1; i++) {
            for(int j = 0; j <= len2; j++) {

                int k = i + j - 1;

                if (i > 0 && dp[i - 1][j] && s1[i - 1] == s3[k]) {
                    dp[i][j] = true;
                }

                if (j > 0 && dp[i][j - 1] && s2[j - 1] == s3[k]) {
                    dp[i][j] = true;
                }
            }
        }

        return dp[len1][len2];
    }
};

 

 

Python3

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        len1 = len(s1)
        len2 = len(s2)
        len3 = len(s3)

        if len1 + len2 != len3:
            return False

        dp = [[False] * (len2 + 1) for _ in range(len1 + 1)]
        dp[0][0] = True

        for i in range(len1+1):
            for j in range(len2+1):

                k = i + j -1

                if i > 0 and dp[i-1][j] and s1[i-1] == s3[k]:
                    dp[i][j] = True
                if j > 0 and dp[i][j-1] and s2[j-1] == s3[k]:
                    dp[i][j] = True

        
        return dp[len1][len2]

 

Java

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        if (len1 + len2 != len3) {
            return false;
        }

        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;

        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                int k = i + j - 1;

                if (i > 0 && dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(k)) {
                    dp[i][j] = true;
                }
                if (j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(k)) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[len1][len2];
    }
}