很显然的DP，基本算是一次过了，
比较简单！
1 class Solution { 2 public: 3 bool isInterleave(string s1, string s2, string s3) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 int n1 = s1.size(); 7 int n2 = s2.size(); 8 int n3 = s3.size(); 9 vector<vector<int> > sat; 10 vector<int> temp(n2, -1); 11 for (int i = 0; i < n1; ++i) { 12 sat.push_back(temp); 13 } 14 return inter(sat, s1, 0, s2, 0, s3, 0); 15 } 16 bool inter(vector<vector<int> > &sat, string &s1, int b1, string &s2, int b2, string &s3, int b3) { 17 if (b1 == s1.size() && b2 == s2.size() && b3 == s3.size()) { 18 return true; 19 } 20 if ((s1.size() + s2.size()) != s3.size()) { 21 return false; 22 } 23 if (b1 == s1.size()) { 24 string ts2 = s2.substr(b2, s2.size() - b2); 25 string ts3 = s3.substr(b3, s3.size() - b3); 26 if (ts2 == ts3) { 27 return true; 28 } 29 return false; 30 } 31 if (b2 == s2.size()) { 32 string ts1 = s1.substr(b1, s1.size() - b1); 33 string ts3 = s3.substr(b3, s3.size() - b3); 34 if (ts1 == ts3) { 35 return true; 36 } 37 return false; 38 } 39 if (sat[b1][b2] != -1) { 40 return sat[b1][b2]; 41 } 42 if (s1[b1] != s2[b2]) { 43 if (s3[b3] == s1[b1]) { 44 bool res = inter(sat, s1, b1 + 1, s2, b2, s3, b3 + 1); 45 sat[b1][b2] = res; 46 return res; 47 } 48 if (s3[b3] == s2[b2]) { 49 bool res = inter(sat, s1, b1, s2, b2 + 1, s3, b3 + 1); 50 sat[b1][b2] = res; 51 return res; 52 } 53 sat[b1][b2] = false; 54 return false; 55 } 56 else { 57 if (s3[b3] == s1[b1]) { 58 bool res = inter(sat, s1, b1 + 1, s2, b2, s3, b3 + 1) || inter(sat, s1, b1, s2, b2 + 1, s3, b3 + 1); 59 sat[b1][b2] = res; 60 return res; 61 } 62 sat[b1][b2] = false; 63 return false; 64 } 65 } 66 };