Java DFA solution, with better structure and easy understand


  • 2
    R
    public boolean isMatch(String s, String p) {return matchHere(s,p,0,0);
    }
    
    private boolean matchHere(String s, String p, int indexS, int indexP){
        if(indexS>=s.length()){
            return isPatternTailingMatch(p,indexP);
        }
        if(indexP>=p.length()){
            return isPatternEndWithWildCard(p);
        }
        if(s.charAt(indexS)==p.charAt(indexP)||p.charAt(indexP)=='?'){
            return matchHere(s,p,indexS+1,indexP+1);
        }
        else if(p.charAt(indexP)=='*'){
            return matchWildCard(s,p,++indexS,indexP+1);
        }
        return false;
    }
    private boolean isPatternTailingMatch(String p, int indexP){
        for(int index=indexP; index<p.length();index++){
            if(p.charAt(index)!='*'){
                return false;
            }
        }
        return true;
    }
    private boolean isPatternEndWithWildCard(String p){
        return p.endsWith("*");
    }
    private boolean matchWildCard(String s, String p, int indexS, int indexP){
        for(int index=indexS;index<s.length();index++){
            if(matchHere(s,p,index,indexP)){
                return true;
            }
        }
        return false;
    }

  • 0
    M

    Very cool! This helped.


  • 0
    M

    I'd like to suggest a change to deal with cases like s="a" p="a".
    In function matchHere, replace
    else if(p.charAt(indexP)=='
    '){
    return matchWildCard(s,p,++indexS,indexP+1);
    }

    with
    else if(p.charAt(indexP)=='*'){
    return matchWildCard(s,p,indexS,indexP+1);
    }

    That is start checking for remaining pattern to be matched from the same position in S instead of next.


Log in to reply
 

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