Leetcode之Interleaving String

题目：

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

代码：

1 递归法（从一至终）：

bool helper(string& s1, int i, string& s2, int j, string& s3, int k) { if (k >= s3.length())return true; if (i >= s1.length() && j >= s2.length())return false; if (i >= s1.length()) { if (s2.substr(j) == s3.substr(k))return true; else return false; } if (j >= s2.length()) { if (s1.substr(i) == s3.substr(k))return true; else return false; } if (s1[i] == s3[k] && s2[j] != s3[k]) { return helper(s1, i + 1, s2, j, s3, k + 1); } else if (s2[j] == s3[k] && s1[i] != s3[k]) { return helper(s1, i, s2, j + 1, s3, k + 1); } else if (s1[i] == s3[k] && s2[j] == s3[k]) { return(helper(s1, i + 1, s2, j, s3, k + 1) || helper(s1, i, s2, j + 1, s3, k + 1)); } else return false; return false; } bool isInterleave(string s1, string s2, string s3) { int len1 = s1.length(); int len2 = s2.length(); int len3 = s3.length(); if (len3 != len1 + len2)return false; bool b = helper(s1, 0, s2, 0, s3, 0); return b; }

2 二分递归法

bool isInterleave(string s1, string s2, string s3) { int len1 = s1.length(); int len2 = s2.length(); int len3 = s3.length(); if (len3 != len1 + len2)return false; if (s1 + s2 == s3||s2+s1==s3)return true; if (s1 == "" || s2 == "")return false; int t = len3 / 2; for (int i = 0; i <=len1; i++) { bool b1 = isInterleave(s1.substr(0, i), s2.substr(0, t - i), s3.substr(0, t)); if (!b1)continue; bool b2 = isInterleave(s1.substr(i), s2.substr(t - i), s3.substr(t)); if (b2)return true; else continue; } return false; } };

3 动态规划法

bool isInterleave(string s1, string s2, string s3) { if (s1.size() + s2.size() != s3.size()) return false; int n1 = s1.size(), n2 = s2.size(); vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1)); dp[0][0] = true; for (int i = 1; i <= n1; ++i) { dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]); } for (int i = 1; i <= n2; ++i) { dp[0][i] = dp[0][i - 1] && (s2[i - 1] == s3[i - 1]); } for (int i = 1; i <= n1; ++i) { for (int j = 1; j <= n2; ++j) { dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]); } } return dp[n1][n2]; }

想法：动态规划法比递归法节省时间