[Java] My recursive top down solution


  • 0
    L
    public class Solution {
        public int[][] state;
        
        public boolean isInterleave(String s1, String s2, String s3) {
            int l1 = s1.length()+1;
            int l2 = s2.length()+1;
            state = new int[l1][l2];
            int i,j;
            for(i=0;i<l1;i++){
                for(j=0;j<l2;j++){
                    state[i][j] = -1;
                }
            }
            
            if(s1.length()+s2.length()!=s3.length()) return false;
            
            return isInterleave2(s1,s2,s3);
        }
        
        public boolean isInterleave2(String s1, String s2, String s3) {
            if(state[s1.length()][s2.length()] != -1){
                return    state[s1.length()][s2.length()]>0 ;
            }
            if(s1.length()==0 && s2.length()!=0){
                state[s1.length()][s2.length()] = s2.equals(s3) ? 1 : 0;
                return s2.equals(s3);
            } 
            else if(s1.length()!=0 && s2.length()==0){ 
                state[s1.length()][s2.length()] = s1.equals(s3) ? 1 : 0;
                return s1.equals(s3);
            }
            else if(s1.length()==0 && s2.length()==0){ 
                state[s1.length()][s2.length()] = 1;
                return true;
            }
            
            if(s3.charAt(0)==s1.charAt(0) && s3.charAt(0)==s2.charAt(0)){
                state[s1.length()][s2.length()] = isInterleave2(s1.substring(1),s2,s3.substring(1))||isInterleave2(s1,s2.substring(1),s3.substring(1)) ? 1 : 0;
                return state[s1.length()][s2.length()]>0;
            }
            else if(s3.charAt(0)!=s1.charAt(0) && s3.charAt(0)==s2.charAt(0)){
                state[s1.length()][s2.length()] = isInterleave2(s1,s2.substring(1),s3.substring(1)) ? 1 : 0;
                return state[s1.length()][s2.length()]>0;
            }
            else if(s3.charAt(0)==s1.charAt(0) && s3.charAt(0)!=s2.charAt(0)){
                state[s1.length()][s2.length()] = isInterleave2(s1.substring(1),s2,s3.substring(1)) ? 1 : 0;
                return state[s1.length()][s2.length()]>0;
            }
            
            state[s1.length()][s2.length()] = 0;
            return false;
        }
    }

Log in to reply
 

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