C++ recursive DFS readable solution with detailed explanation

  • 1

    The idea is to pre-process pattern string pinto characters with indication whether they are "fuzzy" match or not, which is to save all '.'and alphabet characters of p paired with a flag of "fuzzy" into vector<pair<char, bool>> psin the original order in p. Note that if we encounter a fuzzy match of type ".*", we can simply ignore any consecutive following fuzzy matches. For example, p=".*a*.*f*bcd"is equivalent to p=".*bcd". However, any "." cannot be ignored since each such pattern enforces the string length to be exact 1 character count.

    Then we will match characters in swith ps[i]one by one. Based on matching types, we have

    • Non fuzzy match: if current character in smatches with ps[i].first, continue to match next character with ps[i+1].first; otherwise, cannot be matched.
    • Fuzzy match: for any length between 0 and remaining length of unchecked s, do non fuzzy type match with identical character ps[i+1].first.
        vector<pair<char, bool>> ps;
        bool isMatch(string s, string p) {
          for (auto i = p.begin(); i != p.end(); ++i) { // build ps[]
            bool fuzzy_match = (i+1 != p.end() && *(i+1) == '*');  
            if (fuzzy_match && !ps.empty() && ps.back() == make_pair('.',true)) i++;
            else ps.emplace_back(fuzzy_match? *i++:*i, fuzzy_match);
          return dfs(s, 0);
        bool dfs(const string& s, int i) {
          if (i == ps.size()) return s.empty();
          char c = ps[i].first;
          if (!ps[i].second) // non fuzzy match
            return (s.empty() || c != '.' && s[0] != c)? false : dfs(s.substr(1), i+1);
          for (int j = 0; j <= s.length(); ++j) // fuzzy match
            if (c != '.' && j && s[j-1] != c) return false;
            else if (dfs(s.substr(j), i+1)) return true;
          return false;

Log in to reply

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