# Wrong answer with input "a", "", "a"?

• 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];
}
}``````

• Got it! It should be s1.substring(0, i).equals(s3.substring(0, i)) rather than ==.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.