2014
11-19

# LeetCode-Interleaving String[动态规划]

### Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

\begin{Code}
f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j])
|| (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);
\end{Code}

// LeetCode, Interleaving String
// 递归，会超时，仅用来帮助理解
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s3.length() != s1.length() + s2.length())
return false;

return isInterleave(begin(s1), end(s1), begin(s2), end(s2),
begin(s3), end(s3));
}

template<typename InIt>
bool isInterleave(InIt first1, InIt last1, InIt first2, InIt last2,
InIt first3, InIt last3) {
if (first3 == last3)
return first1 == last1 && first2 == last2;

return (*first1 == *first3
&& isInterleave(next(first1), last1, first2, last2,
next(first3), last3))
|| (*first2 == *first3
&& isInterleave(first1, last1, next(first2), last2,
next(first3), last3));
}
};


// LeetCode, Interleaving String
// 二维动规，时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s3.length() != s1.length() + s2.length())
return false;

vector<vector<bool>> f(s1.length() + 1,
vector<bool>(s2.length() + 1, true));

for (size_t i = 1; i <= s1.length(); ++i)
f[i][0] = f[i - 1][0] && s1[i - 1] == s3[i - 1];

for (size_t i = 1; i <= s2.length(); ++i)
f[0][i] = f[0][i - 1] && s2[i - 1] == s3[i - 1];

for (size_t i = 1; i <= s1.length(); ++i)
for (size_t j = 1; j <= s2.length(); ++j)
f[i][j] = (s1[i - 1] == s3[i + j - 1] && f[i - 1][j])
|| (s2[j - 1] == s3[i + j - 1] && f[i][j - 1]);

return f[s1.length()][s2.length()];
}
};


// LeetCode, Interleaving String
// 二维动规+滚动数组，时间复杂度O(n^2)，空间复杂度O(n)
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.length() + s2.length() != s3.length())
return false;

if (s1.length() < s2.length())
return isInterleave(s2, s1, s3);

vector<bool> f(s2.length() + 1, true);

for (size_t i = 1; i <= s2.length(); ++i)
f[i] = s2[i - 1] == s3[i - 1] && f[i - 1];

for (size_t i = 1; i <= s1.length(); ++i) {
f[0] = s1[i - 1] == s3[i - 1] && f[0];

for (size_t j = 1; j <= s2.length(); ++j)
f[j] = (s1[i - 1] == s3[i + j - 1] && f[j])
|| (s2[j - 1] == s3[i + j - 1] && f[j - 1]);
}

return f[s2.length()];
}
};


Java代码:

public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();
if(m + n != s3.length()) return false;

int dp[][] = new int[m+1][n+1];

dp[0][0] = 0;
for(int i=1; i<=m; i++)
if(s1.charAt(i-1) == s3.charAt(i-1))
dp[i][0] = dp[i-1][0]+1;
else break;

for(int i=1; i<=n; i++)
if(s2.charAt(i-1) == s3.charAt(i-1))
dp[0][i] = dp[0][i-1]+1;
else break;
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp[i][j] = dp[i-1][j] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp[i][j] = Math.max(dp[i][j-1] + 1, dp[i][j]);
}
}

return dp[m][n] == s3.length();
}
}