LC97: Interleaving String

작성일

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

  • 흔한 문자열 DP 문제, LCS 같은 거랑 매우 유사하다.
  • dp[i][j]의 의미를 s1[i-1] mix s2[j-1] = s3[i+j-1]인지 아닌지로 보면 된다.
  • 그러면 dp[i][j]는 아래와 같을때 참이다.
    • dp[i-1][j]이 참이고 s1[i-1] == s3[i+j-1]이거나
    • dp[i][j-1]이 참이고 s2[j-1] == s3[i+j-1]이거나
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.size()+s2.size() != s3.size()) return false;
        vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1));
        dp[0][0] = 1;
        for(int i = 0; i < s1.size() && s1[i] == s3[i]; i++)
            dp[i+1][0] = true;
        for(int i = 0; i < s2.size() && s2[i] == s3[i]; i++)
            dp[0][i+1] = true;
        for(int i = 1; i <= s1.size(); i++) {
            for(int j = 1; j <= s2.size(); j++) {
                if(dp[i-1][j] && s1[i-1] == s3[i+j-1]) dp[i][j] = true;
                if(dp[i][j-1] && s2[j-1] == s3[i+j-1]) dp[i][j] = true;
            }
        }
        return dp[s1.size()][s2.size()];
    }
};