第一次dfs， 没过large， 马上想到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 if (s3.size() != s1.size()+s2.size()) return false; 7 int m = s1.size(); 8 int n = s2.size(); 9 vector<vector<bool>> f(m+1, vector<bool>(n+1)); 10 f[0][0] = true; 11 for (int i = 1; i <= m; i++) { 12 f[i][0] = s1[i-1] == s3[i-1]? f[i-1][0]:false; 13 } 14 for (int i = 1; i <= n; i++) { 15 f[0][i] = s2[i-1] == s3[i-1]? f[0][i-1]:false; 16 } 17 for (int i = 1; i <= m; i++) { 18 for (int j = 1; j <= n; j++) { 19 f[i][j] = (f[i-1][j] && s1[i-1] == s3[i+j-1]) || (f[i][j-1] && s2[j-1] == s3[i+j-1]); 20 } 21 } 22 return f[m][n]; 23 } 24 };
C#
1 public class Solution { 2 public bool IsInterleave(string s1, string s2, string s3) { 3 if (s3.Length != s1.Length + s2.Length) return false; 4 bool[,] f = new bool[s1.Length+1, s2.Length+1]; 5 f[0, 0] = true; 6 for (int i = 1; i <= s1.Length; i++) { 7 f[i, 0] = s1[i-1] == s3[i-1]? f[i-1, 0] : false; 8 } 9 for (int i = 1; i <= s2.Length; i++) { 10 f[0, i] = s2[i-1] == s3[i-1]? f[0, i-1] : false; 11 } 12 for (int i = 1; i <= s1.Length; i++) { 13 for (int j = 1; j <= s2.Length; j++) { 14 f[i, j] = (f[i-1, j] && s1[i-1] == s3[i+j-1]) || (f[i, j-1] && s2[j-1] == s3[i+j-1]); 15 } 16 } 17 return f[s1.Length, s2.Length]; 18 } 19 }