Interleaving String
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