Simple solution in Java


  • 0
    D
    public class Solution {
        
        int[][] checkedPaths;
        
        public boolean isInterleave(String s1, String s2, String s3) {
            if(s1.length() + s2.length() != s3.length())
                return false;       
                
            checkedPaths = new int[s1.length()][s2.length()];
            
            for(int i = 0 ; i < s1.length() ; i++){
                for(int j = 0 ; j < s2.length() ; j++){
                    checkedPaths[i][j] = -1;
                }
            }
            
            return checkNext(s1, s2, s3);
        }
        
        private boolean checkNext(String s1, String s2, String s3){
            if(s3.length() == 0)
                return true;
    
            if(s1.length() == 0)
                return s2.equals(s3);
            
            if(s2.length() == 0)
                return s1.equals(s3);
            
            if(checkedPaths[s1.length() - 1][s2.length() - 1] == 1){
                return false;
            } else{
                checkedPaths[s1.length() - 1][s2.length() -1] = 1;
            }
            
            boolean s1Match = s1.charAt(0) == s3.charAt(0);
            boolean s2Match = s2.charAt(0) == s3.charAt(0);
            
            if(s1Match && s2Match){
                return ( checkNext(s1.substring(1), s2, s3.substring(1)) || checkNext(s1, s2.substring(1), s3.substring(1)) );
            } else if(s1Match){
                return checkNext(s1.substring(1), s2, s3.substring(1));
            } else if(s2Match){
                return checkNext(s1, s2.substring(1), s3.substring(1));
            } else {
                return false;
            }
        }
    }

Log in to reply
 

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