[Java] Share my solution with comments


  • 1
    L

    This problem could be solved by dynamic programming. But some features make this one special, such that linear time solution exists.

    If we have p = s1s2s3s4*, s1,s2,s3,s4 are all strings and are concatenated sequentially,
    and string s contains multiple substrings s1, i.e s = ...s1..s1...s1..., then the first substring should be selected to be matched with s1 in p. The original problem is equal to matching problem between s2s3s4 and rest of p starting from the end of s1.

    For example, p=aabbcc and s=abaaabbbaa, s has three substring aa, i.e. abaaabbbaa , abaaabbbaa, and abaaabbbaa. Matching problem between s and p is equivalent as problem between bbcc* and abbbaa.

     public class Solution {
            public boolean isMatch(String s, String p) {
                int ss=0,pp=0;
                int marked = -1;
                String p2 = p+'^'; // In case that the last char in p is *
        
                while(ss<s.length() && pp<p2.length()){
                    if(s.charAt(ss) == p2.charAt(pp) || p2.charAt(pp)=='?'){
                        ss++;
                        pp++;
                    }
                    else if(p2.charAt(pp)=='*'){
                        pp++;
                        marked = pp;
                    }
                    else{
                        if(pp==marked){
                            ss++;
                        }
                        else{
                            if(marked!=-1){ 
                                ss = ss - (pp - marked - 1);
                                pp = marked;
                            }
                            else return false;
                        }
                    }
                }
                
                while(pp<p.length()){
                    if(p.charAt(pp)!='*'){
                        return false;
                    }
                    pp++;
                }
                return ss>=s.length();
            }
        }

  • 3
    L

    Your code works for the OJ. But I don't really see the correlation between the code and the explanation.

    The critical part of the code is

    if(marked!=-1){ 
        ss = ss - (pp - marked - 1);
        pp = marked;
    }
    else return false;
    

    which I tried to find an example to make sense of it.

    I think the key idea of this code snippet is to backtrack to another substring in S that can be matched with the wildcard '*' in pattern P.

    Voila. Here is the example that I found.

    S="abbd"
    P="*bd"
    

    There are two ‘b’ in S that can be matched with the one in the pattern P.
    In the first round of the execution, the first ‘b’ in S would be matched with the ‘b’ in P, and accordingly ‘a’ is matched with the wild card ‘*’. Then it would hit the code snippet above at the second ‘b’ in S, which it does not match with the ‘d’ in P.

    Therefore, the matching is backtracked to the second ‘b’ in S and start the matching over, i.e. this time we match the wildcard ‘*’ with the substring “ab” instead of “a”. At the end, we found the matching between the string and the pattern.


Log in to reply
 

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