I use DP as the solution. Following is my code which got wrong answer with input "a", "", "a".

The state[i][j] stores whether substring ending at i of S1 and substring ending at j of S2 can interleave substring ending at i + j of S3.

```
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();
if (s3.length() != m + n) {
return false;
}
boolean[][] state = new boolean[m + 1][n + 1];
state[0][0] = true;
for (int i = 1; i <= m; i++) {
//state[i][0] = (state[i-1][0] && s1.charAt(i - 1) == s3.charAt(i - 1));
state[i][0] = s1.substring(0, i) == s3.substring(0, i);
}
for (int j = 1; j <= n; j++) {
state[0][j] = (state[0][j-1] && s2.charAt(j - 1) == s3.charAt(j - 1));
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
state[i][j] = (state[i][j-1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) ||
(state[i-1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
}
}
return state[m][n];
}
}
```

But when I changed my code only a little. It is accepted. And when I try both of them on my computer. Both of them works. And I think there is no difference between the two. Can anyone figure out why?

```
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();
if (s3.length() != m + n) {
return false;
}
boolean[][] state = new boolean[m + 1][n + 1];
state[0][0] = true;
for (int i = 1; i <= m; i++) {
//where different with the first
state[i][0] = (state[i-1][0] && s1.charAt(i - 1) == s3.charAt(i - 1));
//state[i][0] = s1.substring(0, i) == s3.substring(0, i);
}
for (int j = 1; j <= n; j++) {
state[0][j] = (state[0][j-1] && s2.charAt(j - 1) == s3.charAt(j - 1));
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
state[i][j] = (state[i][j-1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) ||
(state[i-1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
}
}
return state[m][n];
}
}
```