Short Java DP Solution


  • 0
    M
        public boolean isInterleave(String s1, String s2, String s3) {
            if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) return false;
            int n1 = s1.length(), n2 = s2.length();
            boolean[][] isInter = new boolean[n1 + 1][n2 + 1];
            for (int i = 0; i <= n1; ++i) {
                for (int j = 0; j <= n2; ++j) {
                    if (i == 0 && j == 0) isInter[i][j] = true;
                    else isInter[i][j] = i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1) && isInter[i - 1][j] 
                        || j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1) && isInter[i][j - 1];
                }
            }
            return isInter[n1][n2];
        }
    

Log in to reply
 

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