Leetcode 97: Interleaving String (iterative dp)

leetcode_97b.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isInterleave(string s1, string s2, string s3) {
    if (s1.size() + s2.size() != s3.size()) return false;
    vector<vector<bool>> dp(s1.size()+1, vector<bool>(s2.size()+1, false));
    if (s3.size() == 0) return true;
    dp[0][0] = true;

    for (int c=1; c<=s2.size(); ++c) {
        if (dp[0][c-1] && s2[c-1]==s3[c-1]) dp[0][c] = true;
    }
    for (int r=1; r<=s1.size(); ++r) {
        if (dp[r-1][0] && s1[r-1]==s3[r-1]) dp[r][0] = true;
    }
    for (int r=1; r<=s1.size(); ++r) {
        for (int c=1; c<=s2.size(); ++c) {
            if (dp[r][c-1] && s2[c-1]==s3[r+c-1]) dp[r][c]=true;
            if (dp[r-1][c] && s1[r-1]==s3[r+c-1]) dp[r][c]=true;
        }
    }
    return dp[s1.size()][s2.size()];
}

int main() {
    string s1 = "aabaac";
    string s2 = "aadaaeaaf";
    string s3 = "aadaaeaabaafaac";
//    string s1 = "aabcc";
//    string s2 = "dbbca";
//    string s3 = "aadbbbaccc"; //"aadbbcbcac";
    cout << isInterleave(s1, s2, s3) << "\n";
    return 0;
}