Well commented Java Solution using two stacks, beats 61% of the solutions.


  • 0
    B
    public static boolean isMatch(String s, String p) {
             Stack<Integer> starPosition = new Stack<Integer>();
            Stack<Integer> stringPosition = new Stack<Integer>();
            int i = 0, j= 0;
            boolean active = false;
            int len1= p.length(), len2=s.length() ;
            while(i<len1 && j<len2){
                char c = p.charAt(i);
                char d = s.charAt(j);
                if(c == d || c == '?'){
                    //store the position of the characters you have skipped because of a *, next
                    //time you would start from this position + 1. More to follow about this.....
                    if(active){
                        stringPosition.push(j);
                    }
                    i++;
                    j++;
                    active = false;
                }
                else if(c=='*'){
                    //skip consecutive *s
                     while(i<len1 && p.charAt(i)=='*'){
                         i++;
                     }
                    active = true;
                    
                    //* followed by ? needs you to skip no.of characters equal to the number of '?' while still
                    //mainatining the active status
                    while(i<len1 &&p.charAt(i)=='?'){
                        i++;
                        j++;
                    }
                    starPosition.push(i-1);
                }
                else if(c != d && active){
                    j++;
                }
                else {
                    if(starPosition.isEmpty() || stringPosition.isEmpty() ){
                        break;
                    }
                    else {
                        //....here it is.
                        // you want to start from the position after the previous match
                        i = starPosition.pop();
                        i++;
                        starPosition.push(i-1);
                        j = stringPosition.pop();
                        j++;
                        active = true;
                    }
                }
                if(i==len1&&j<len2){
                    if(starPosition.isEmpty() || stringPosition.isEmpty()){
                        break;
                    }
                    else {
                        i = starPosition.pop();
                        i++;
                        starPosition.push(i-1);
                        j = stringPosition.pop();
                        j++;
                        active = true;
                    }
                }
            }
            //* at the end can simply be skipped
            while(i<len1 && p.charAt(i)=='*'){
                    i++;
                    active = true;
            }
            if(i==len1&&(j==len2||(j<=len2 && active)))
                return true;
            else 
                return false;
            
        }
    

Log in to reply
 

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