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


  • 0
    N

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

  • 0
    N

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


Log in to reply
 

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