1ms java recursive code


  • 0
    J
    public class Solution {
    boolean[][] notValid = null;
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length()){
            return false;
        }
        notValid = new boolean[s1.length()+1][s2.length()+1];
        return isInterleave(s1, 0, s2, 0, s3);
    }
    private boolean isInterleave(String s1, int i, String s2, int j, String s3){
        if(notValid[i][j]){
            return false;
        }
        if(i>=s1.length()||j>=s2.length()){
            boolean isTrue = (i>=s1.length())?s2.substring(j).equals(s3.substring(i+j)):s1.substring(i).equals(s3.substring(i+j));
            if(isTrue){
                return true;
            }
            else{
                notValid[i][j] = true;
                return false;
            }
        }
        if(s1.charAt(i)==s3.charAt(i+j)&&isInterleave(s1, i+1, s2, j, s3)){
            return true;
        }
        if(s2.charAt(j)==s3.charAt(i+j)&&isInterleave(s1, i, s2, j+1, s3)){
            return true;
        }
        notValid[i][j] = true;
        return false;
    }
    

    }


Log in to reply
 

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