# 0097. Interleaving String
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/interleaving-string/
## 思路

## Code

class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length()!=s3.length()) return false;
StringBuilder str1 = new StringBuilder();
str1.append('#');
str1.append(s1);
StringBuilder str2 = new StringBuilder();
str2.append('#');
str2.append(s2);
int m = s1.length(), n = s2.length();
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for(int i=1; i<=m; i++){
if(dp[i-1][0] && str1.charAt(i)==s3.charAt(i-1)) dp[i][0]=true;
}
for(int i=1; i<=n; i++){
if(dp[0][i-1] && str2.charAt(i)==s3.charAt(i-1)) dp[0][i]=true;
}

for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(str1.charAt(i)==s3.charAt(i+j-1) && dp[i-1][j]) dp[i][j] = true;
if(str2.charAt(j)==s3.charAt(i+j-1) && dp[i][j-1]) dp[i][j] = true;
}
}
return dp[m][n];
}
}