Java 3ms beats 97.99%


  • 1
    J

    Key ideas here:

    • Backtracking, optimized with dynamic programming.

    • Iterate through the simple tokens to minimize recursive calls.

    public class Solution {
        
        char[] s, p;
        int sLength, pLength, noWildcard;
        Boolean[][] dp;
        
        public boolean isMatch(String ss, String ps) {
            
            s = ss.toCharArray();
            p = ps.toCharArray();
            sLength = s.length;
            pLength = p.length;
            noWildcard = pLength - 1;
            dp = new Boolean[pLength + 1][sLength + 1];
            return isMatch(0, 0);
        }
        
        boolean isMatch(int pi, int si){
            if(dp[pi][si] != null) return dp[pi][si];
            while(true){
        
                if(pi < noWildcard && p[pi+1] == '*'){
                    char c = p[pi];
                    pi += 2;
                    
                    while(true){
                        
                        boolean isMatch = isMatch(pi, si);
                        dp[pi][si] = isMatch;
                        
                        if(isMatch){
                            return true;
                        }
                        
                        if(si == sLength) return pi == pLength;
                        
                        if(c != '.' && c != s[si]){
                            return false;
                        }
                        
                        si++;
                    }
                }
                
                if(pi == pLength || si == sLength) return pi == pLength && si == sLength;
                
                if(p[pi] != '.' && p[pi] != s[si]){
                    return false;
                }
                
                pi++;
                si++;
            }
        }
    }

  • 0
    Z

    Sorry,but I find your program may has a bug.When input "aa" and "a*",the result is not right.


  • 0
    B

    27 ms beat 46%. test on Sep 20.


  • 0

    @Bruce This actually beats 99.54% when I tested it.


  • 0
    B

    @zhugejunwei I just test it and find
    "445 / 445 test cases passed.
    Status: Accepted
    Runtime: 36 ms
    You are here!
    Your runtime beats 45.33% of java submissions. " now it is 14:41:57 Nov 2, 2016

    14:41


  • 0

    @Bruce Copy others' solution and test the time performance, and challenge what the PS said, I think it's not a good idea, useless actually.

    This is a good solution, and it has a very good time performance.

    If you don't like it, u can just ignore it. Please don't argue with someone on this kind of useless things.


  • 0
    B

    @zhugejunwei I did not argue it with anybody. I just marked it according to test result. It is helpful for later reader especially when some guy want find some efficient solution, with this mark, they need not to copy, test any more.
    It is common that the performance changes from time to time as the test data changes from time to time . Please see the record. It is you who started the argue, not me.


  • 0
    B

    @Bruce I test again. this is the screenshot.
    0_1478125084905_Screen Shot 2016-11-02 at 3.15.44 PM.png


Log in to reply
 

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