Sharing My Java Accepted Solution...


  • 0
    D

    the idea is when finds a star and fail, it will force the previous star check loop to fail too. this way eliminates the unnecessary checks so the program will not run out of time. accepted 60 ms java solution.

    public class Solution {
        public boolean isMatch(String s, String p) {
            return isMatch(s.toCharArray(), p.toCharArray(), 0, 0)>0;
        }
        
        private int isMatch(char[] s, char[] p, int indexS, int indexP) {
            int _false = 0, _true = 1;
            while (indexS<s.length) {
                if (indexP==p.length) return _false;
                if (p[indexP]=='?'||p[indexP]==s[indexS]) {
                    indexS++;
                    indexP++;
                } else if (p[indexP]=='*') {
                    _false = -1;
                    while (++indexP<p.length) if (p[indexP]!='*') break;
                    if (indexP==p.length) return _true;
                    while (indexS<s.length) {
                        int trial = isMatch(s,p,indexS++,indexP);
                        if (trial>0) return _true;
                        else if (trial<0) return _false;  //find another star and still fail, no need to continue
                    }
                } else {
                    return _false;
                }
            }
            
            while (indexP<p.length) if (p[indexP++]!='*') return _false;
            return _true;
        }
    }
    

Log in to reply
 

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