1 ms JAVA DP Solution - Beats 94%


  • 0
    B

    My approach to most DP problems is simple:

    1. Create a backtracking code
    2. Use a HashMap/Array to memoize results

    I did the same here as well. Also, instead of using the substring function for each recursive call, I decided to use the index instead. It made my function signature look crappy but helped me use a matrix (which is faster) rather than a complex HashMap with a list of Strings as its key.

    My code is as follows:

    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            int[][] memo = new int[s1.length() + 1][s2.length() + 1];
            return helper(s1, s2, s3, 0, 0, 0, memo);
        }
        
        private boolean helper(String s1, String s2, String s3, int index1, int index2, int index3, int[][] memo) {
            if(s1.length() + s2.length() != s3.length()) return false;
            if(s1.length() == index1 && s2.length() == index2  && s3.length() == index3 ) return true;
    
            boolean s1flag = false;
            boolean s2flag = false;
            
            if(index1 < s1.length() && s1.charAt(index1) == s3.charAt(index3)) {
                if(memo[index1+1][index2] == 1) {
                    s1flag = true;
                } else if(memo[index1][index2] == 0){
                    s1flag = helper(s1, s2, s3, index1+1, index2, index3+1, memo);
                    memo[index1+1][index2] = s1flag ? 1 : -1;
                }
            }
            
            if(index2 < s2.length() && s2.charAt(index2) == s3.charAt(index3)) {
                if(memo[index1][index2+1] == 1) {
                    s2flag = true;
                } else if(memo[index1][index2] == 0){
                    s2flag = helper(s1, s2, s3, index1, index2 + 1, index3 + 1, memo);
                    memo[index1][index2+1] = s1flag ? 1 : -1;
                }
            }
            
            return s1flag || s2flag;
        }
    }
    

Log in to reply
 

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