Java DP solution O(m*n) time, O(n) space!


  • 1
    Y
    public class Solution {
        /**
         * Dynamic programming
         * Dynamic programming has 2 properties: overlapping subproblems and optimal substructure. 
         * Then for this question, the overlapping subproblem would be matching substring of s1 or s2 with substring of s3. 
         * Since s3 must match s1 and s2 in a way that the character has the same order, so we can just start comparison from start to end. 
         * Say, s1.charAt(i) == s3.charAt(i + j); then we only have to deal with the subproblem of s1.substring(i + 1, s1.length()), s2.substring(j, s2.length()) and s3.substring(i + j, s3.length())
         * Since we don't have to know exactly how they match but rather only if they have matched for previous characters, a 2-dimensional boolean array would be enough. 
         * One dimension record the index of s1 and the other record the index of s2.
         * matched[i][j] = matched[i][j-1] && current character of s2 and s3 is the same || matched[i-1][j] && current character of s1 and s3 is the same
         * Base case would be matched[0][0] = true
         * The corner case would be s1.length() + s2.length() != s3.length(), which is obviously false. 
         * O(m * n) time and space where m and n are length of s1 and s2 respectively
         * The space may be further optimized to O(n), see below.
         */
        
        public boolean isInterleave(String s1, String s2, String s3) {
            if (s1 == null || s1.length() == 0) {
                return s2.equals(s3);
            }
            if (s2 == null || s2.length() == 0) {
                return s1.equals(s3);
            }
            if (s1.length() + s2.length() != s3.length()) {
                return false;
            }
            
            boolean[][] matched = new boolean[s1.length() + 1][s2.length() + 1];
            char[] ch1 = s1.toCharArray();
            char[] ch2 = s2.toCharArray();
            char[] ch3 = s3.toCharArray();
            
            for (int i = 0; i <= ch1.length; i++) {
                for (int j = 0; j <= ch2.length; j++) {
                    if (i == 0 && j == 0) {
                        matched[i][j] = true;
                    } else if (i == 0) {
                        matched[i][j] = matched[i][j-1] && ch2[j - 1] == ch3[i + j - 1];
                    } else if (j == 0) {
                        matched[i][j] = matched[i - 1][j] && ch1[i - 1] == ch3[i + j - 1];
                    } else {
                        matched[i][j] = (matched[i][j - 1] && ch2[j - 1] == ch3[i + j - 1] || matched[i - 1][j] && ch1[i - 1] == ch3[i + j - 1]);
                    }
                }
            }
            
            return matched[ch1.length][ch2.length];
        }
    

    Since every matched flag is only related to the flag on the right and above it, we can drop every other flags and only retain a 1-dimension array to store these flags.

    public Solution {
        /**
         * Further optimized to O(m * n) time and O(n) space where m and n are the length of s1 and s2 respectively
         */
        public boolean isInterleave(String s1, String s2, String s3) {
            if (s1 == null || s2 == null || s3 == null) {
                return false;
            }
            if (s1.length() + s2.length() != s3.length()) {
                return false;
            }
            
            char[] ch1 = s1.toCharArray();
            char[] ch2 = s2.toCharArray();
            char[] ch3 = s3.toCharArray();
            boolean[] matched = new boolean[ch2.length + 1];
            for (int i = 0; i <= ch1.length; i++) {
                for (int j = 0; j <= ch2.length; j++) {
                    if (i == 0 && j == 0) {
                        matched[j] = true;
                    } else if (i == 0) {
                        matched[j] = matched[j - 1] && ch2[j - 1] == ch3[i + j -1];
                    } else if (j == 0) {
                        matched[j] = matched[j] && ch1[i - 1] == ch3[i + j - 1];
                    } else {
                        matched[j] = matched[j - 1] && ch2[j - 1] == ch3[i + j - 1] || matched[j] && ch1[i - 1] == ch3[i + j - 1];
                    }
                }
            }
            
            return matched[ch2.length];
        }
    }
    

Log in to reply
 

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