Interleaving String

mail@pastecode.io avatar
unknown
c_cpp
21 days ago
734 B
3
Indexable
Never
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) {
            return false;
        }

        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        vector<bool> dp[2] = {std::vector<bool>(s2.size(), false), std::vector<bool>(s2.size(), false)};
        dp[0][0] = true;

        for (int i = 0; i < s1.size(); i++)
            for (int j = 0; j < s2.size(); j++) {
                if (i > 0) dp[i%2][j] = dp[(i - 1)%2][j] && s1[i] == s3[i + j];
                if (j > 0) dp[i%2][j] = dp[i%2][j] || (dp[i%2][j - 1] && s2[j] == s3[i + j]);
            }

        return dp[(s1.size() - 1)%2][s2.size() - 1];
    }
};
Leave a Comment