Java DP Solution, with three pointers


  • 0
    Z

    '''
    public class Solution {

    public boolean doesNumCharsConfirm(String s1, String s2, String s3){
        int chars[] = new int[26];
        for(int i = 0;i<s1.length();i++){
            chars[s1.charAt(i)-'a']++;   
        }
        for(int i = 0;i<s2.length();i++){
            chars[s2.charAt(i)-'a']++;   
        }
        int s3chars[] = new int[26];
        for(int i = 0;i<s3.length();i++){
              s3chars[s3.charAt(i)-'a']++; 
        }
        for(int i = 0;i<26;i++){
            if(chars[i] != s3chars[i]) return false;
        }
        return true;
    }
    int dp[][][];
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length() != s3.length()) return false;
        if(!doesNumCharsConfirm(s1,s2,s3)) return false;
        dp = new int[s3.length()+1][s2.length()+1][s1.length()+1];
        return check(s1,s2,s3,0,0,0);
    }
    
    public boolean check(String s1, String s2, String s3, int p1, int p2, int p3){
        boolean ans = false;
        if(p3 == s3.length() && p1 == s1.length() && p2 == s2.length()) return true;
        if(p3<s3.length()){
            char cur = s3.charAt(p3);
            boolean ok =  false;
            if(p1<s1.length()){
                if(cur == s1.charAt(p1)){
                    ok = true;
                    int np3 = p3+1;
                    int np2 = p2;
                    int np1 = p1+1;
                    if(dp[np3][np2][np1] == 0){
                        dp[np3][np2][np1] = 1; 
                        boolean x = check(s1, s2, s3, np1, np2, np3);
                        if(x) dp[np3][np2][np1] = 2;
                    }
                    ans = ans || dp[np3][np2][np1] == 2;
                }
            } 
            if(ans) return true;
            if(p2<s2.length()){
                if(cur == s2.charAt(p2)){
                    ok = true;
                    int np3 = p3+1;
                    int np2 = p2+1;
                    int np1 = p1;
                    if(dp[np3][np2][np1] == 0){
                        dp[np3][np2][np1] = 1; 
                        boolean x = check(s1, s2, s3, np1, np2, np3);
                        if(x) dp[np3][np2][np1] = 2;
                    }
                    ans = ans || dp[np3][np2][np1] == 2;
                }
            } 
        }
        return ans;
    }
    

    ' ''
    }


Log in to reply
 

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