Java 7ms DFA with comments easy understand


  • 3
    R
    public boolean isMatch(String s, String p) {
            int saved_p=-1, saved_s=-1;
            int indexP=0;
            for(int indexS=0; indexS<s.length();){
    
                if(indexP<p.length() && (s.charAt(indexS)==p.charAt(indexP)||p.charAt(indexP)=='?')){
                    //match to a single character
                    indexP++;
                    indexS++;
                }
                else if(indexP<p.length() && p.charAt(indexP)=='*'){
                    // go into the * state, we need to save the P next position and save S next position
                    // when any mismatch happen, we can revert the search to it previous state '*'
                    saved_p=indexP;
                    //move the saved_s, next time it should skip current one
                    saved_s=indexS+1;
                    indexP++;
                }
                else if(saved_p!=-1){
                    //means not match, we need to revert 
                    indexP=saved_p;
                    indexS=saved_s;
                }
                else{
                    //means not match, but not wildcard
                    return false;
                }
            }
            //examine the left char in the pattern
            //they should all be '*' if any char left
            for(int index=indexP; index<p.length();index++){
                if(p.charAt(index)!='*'){
                    return false;
                }
            }
            return true;
        }

  • 0

    I don't think this method is correct, try testcase:

    "a*aa"
    "a*a"

  • 0
    This post is deleted!

  • 0

    Should make change like this:

    if(indexP<p.length() && (p.charAt(indexP)!='*') && (s.charAt(indexS)==p.charAt(indexP)||p.charAt(indexP)=='?'))
    

  • 0
    P

    I think we wont have '*' in string s


  • 0
    R

    No, we shold consider the start and question marks respectively, just star mark can make the machine state go into the loop state.


  • 0
    L

    Hello, I do not follow the "revert" part and the last loop

    //examine the left char in the pattern
        //they should all be '*' if any char left
        for(int index=indexP; index<p.length();index++){
            if(p.charAt(index)!='*'){
                return false;
            }
        }
    

    Could you please give more explanation?


  • 0
    J

    an * trap for your code!


  • 0
    O

    Well, I don't think this is a DFA solution. Instead, it's a backtracking solution


Log in to reply
 

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