A simple C++ DFS solution, 13-19 ms


  • 0
        bool isMatch(string s, string p) {
            std::function<bool(int, int)> try_match = [&](int i , int j) { 
                if( i == -1 && j == -1) return true;
                if( i < -1 || j < -1 ) return false;
                if(p[j] == '*')
                {
                    if((p[j-1] == s[i] || p[j-1] == '.' ) && try_match(i-1, j)) return true; // match one char
                    if(try_match(i, j-2)) return true; //skip this .*
                }
                else if(p[j] == '.' || p[j] == s[i]) return try_match(i-1, j-1);
                return false;
            };
            return try_match(s.size() - 1, p.size() - 1); // loop from end to front. 
        }
    

    my idea is match from back to front.


Log in to reply
 

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