Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” Output: true Example 2:
Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” Output: false
交错字符串匹配，第一次看到这个题目的时候想到是回溯暴力匹配，但是超时，这是必然的，先上自己想的回溯超时代码，仅仅是记录下自己的思维：
class Solution { public: bool isInterleave(string s1, string s2, string s3) { if (s1.size() == 0 && s2.size() == 0 && s3.size() == 0) return true; if (s3.size() == 0) return false; bool res = false; isInterleave(s1, s2, s3, 0, 0, 0, res); return res; } private: void isInterleave(string& s1, string& s2, string& s3, int s1_start, int s2_start, int s3_start, bool &res) { if (s3_start == s3.size() && s1_start == s1.size() && s2_start == s2.size()) { res = true; return; } else { for (int i = s1_start; i < s1.size(); i++) { if (s1.substr(s1_start, i - s1_start + 1) == s3.substr(s3_start, i - s1_start + 1)) isInterleave(s1, s2, s3, i + 1, s2_start, s3_start + i - s1_start + 1, res); else break; } for (int i = s2_start; i < s2.size(); i++) { if (s2.substr(s2_start, i - s2_start + 1) == s3.substr(s3_start, i - s2_start + 1)) isInterleave(s1, s2, s3, s1_start, i + 1, s3_start + i - s2_start + 1, res); else break; } } } };那么这道题应该用什么方法呢，可以考虑这么一个问题，假设现在s1串从[0, i)和s2[0, j)已经组成了一个交错串，也就是说s3[0, i+j-1)已经匹配，那么下一个符合要求的情况是什么呢，很明显就是s1[i] == s3[i+j-1]或者s2[j] == s3[i+j-1]成立，那么动态方程转移过程已经出来了。不废话直接上代码：
class Solution { public: bool isInterleave(string s1, string s2, string s3) { int m = s1.size(); int n = s2.size(); if (s3.size() != s1.size() + s2.size()) return false; vector<vector<bool>> dp(m + 1, (vector<bool>(n + 1, false))); for (int i = 0; i <= s1.size(); i++) { for (int j = 0; j <= s2.size(); j++) { if (i == 0 && j == 0) dp[i][j] = true; else if (i == 0) dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]; else if (j == 0) dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]; else 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])); } } return dp[m][n]; } };