My Java DP Solution, beats 90.90 % of java submissions.


  • 0
    S
    public class Solution {
        public Integer helper(String s1, String s2, String s3, int i, int j, int k, Integer[][] memo) {
            if(i==s1.length()&& j==s2.length())  return 1;
            if(i< s1.length() && j < s2.length() && memo[i][j]!=null) return memo[i][j];
            if(i < s1.length() && j<s2.length() && s1.charAt(i)==s2.charAt(j) && s2.charAt(j) == s3.charAt(k)) 
                memo[i][j] = helper(s1, s2, s3, i+1, j, k+1, memo)==1? 1 : helper(s1, s2, s3, i, j+1, k+1, memo);
            else if(i < s1.length() && s1.charAt(i)==s3.charAt(k)) memo[i][j] = helper(s1, s2, s3, i+1, j, k+1, memo);
            else if(j < s2.length() && s2.charAt(j)==s3.charAt(k)) memo[i][j] = helper(s1, s2, s3, i, j+1, k+1, memo);
            else memo[i][j] = 0;
            return memo[i][j];
        }
        public boolean isInterleave(String s1, String s2, String s3) {
            if(s1.length()+s2.length() != s3.length())
                return false;
            if(s3.length()==0 && (s1.length()!=0 || s2.length()!=0)) return false;
            if((s1.length()==0 && s2.equals(s3)) || (s2.length()==0 && s1.equals(s3))) return true;
            else if(s1.length()==0 || s2.length()==0) return false;
            return helper(s1, s2, s3, 0,0,0, new Integer[s1.length()+1][s2.length()+1])==1? true: false;
            
        }
    }
    

Log in to reply
 

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