This problem can be solved by DP elegantly. You may refer to this link for the code and explanations.
I try to rewrite the code, also in C++, but find that it can only achieve 8ms, not the fastest. I guess handling 2d vector may be more time-consuming and thus optimize it to be ofO(min(m, n)) space, but the running time does not change (still 8ms).
Finally, I find that replacing vector<bool> dp(m, false); with bool* dp = new bool[m + 1]();reduces the running time to 0ms, which is just what I desire. Well, vector is really slow...
The code is finally as follows (well, I do not release the allocated memory of dp, which is not desirable).
1 class Solution { 2 public: 3 bool isInterleave(string s1, string s2, string s3) { 4 int m = s1.length(), n = s2.length(), l = s3.length(); 5 if (m > n) return isInterleave(s2, s1, s3); 6 if (l != m + n) return false; 7 bool *dp = new bool[m + 1](); 8 dp[0] = true; 9 for (int i = 1; i <= m; i++) 10 dp[i] = dp[i - 1] && s3[i - 1] == s1[i - 1]; 11 for (int j = 1; j <= n; j++) { 12 dp[0] = dp[0] && s3[j - 1] == s2[j - 1]; 13 for (int i = 1; i <= m; i++) 14 dp[i] = (dp[i - 1] && s3[i + j - 1] == s1[i - 1]) || (dp[i] && s3[i + j - 1] == s2[j - 1]); 15 } 16 return dp[m]; 17 } 18 };
