Accepted recursive algorithm costs 580ms, how to improve?


  • 0
    Z
    public class Solution {
        public boolean isMatch(String s, String p) {
            if((s.equals(p))||(s.length()==0 && p.length()==0)) return true;
            if(p.length()==0) return false; // return false if p is empty and s is not;
            if(s.length()==0){ //when s is empty and p consists of '*'
            	while(p.length()>0&&p.charAt(p.length()-1)=='*'){
            		p=p.substring(0,p.length()-2);
            	}
            	if(p.length()==0){return true;}
            	else{return false;}
            }
            //check the tail, can check the remain of the two strings
            if(p.charAt(p.length()-1)=='.'||p.charAt(p.length()-1)==s.charAt(s.length()-1)){
                return isMatch(s.substring(0,s.length()-1),p.substring(0,p.length()-1));
            }
            //check the * case;
            if(p.charAt(p.length()-1)=='*'){
                if(p.charAt(p.length()-2)!='.'){
                    int index = s.length()-1;
                    if(isMatch(s,p.substring(0,p.length()-2))) return true;
                    while(index>=0 && s.charAt(index)==p.charAt(p.length()-2)){
                        if(isMatch(s.substring(0,index),p.substring(0,p.length()-2))) return true;
                        index--;
                    }
                }
                if(p.charAt(p.length()-2)=='.'){
                    for(int index = s.length();index>=0;index--){
                        if(isMatch(s.substring(0,index),p.substring(0,p.length()-2))) return true;
                    }
                }
            }
            return false;
        }
    }

Log in to reply
 

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