---
# System prepended metadata

title: 0097. Interleaving String
tags: [Leetcode, Dynamic Programming, Medium]

---

# 0097. Interleaving String
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/interleaving-string/
## 思路
```dp[i][j] => s[1:i]和t[1:j]```能否交叠组成字符串```w[1:i+j]```
## Code
```java=
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];
    }
}
```