C++ Iterative backtracking


  • 0
    G

    This code is modified from My three C++ solutions (iterative (16ms) & DP (180ms) & modified recursion (88ms)) by dong.wang.1694, not sure why the original code could pass the test since clearly it overflows.

    The iterative backtracking is as straightforward as recursion but is way faster.

    class Solution
    {
     public:
      bool isMatch(string s, string p)
      {
        int i = 0, j = 0;
        for (int i0 = -1, j0 = -1; i < s.size(); ++j) {
          if (j == p.size()) {
            if (i0 < 0) return false;
            i = ++i0;
            j = j0;
          } else if ('*' == p[j]) {
            i0 = i;
            j0 = j;
          } else if (s[i++] != p[j] && '?' != p[j]) {
            if (i0 < 0) return false;
            i = ++i0;
            j = j0;
          }
        }
    
        for (; j < p.size() && '*' == p[j]; ++j)
          ;
    
        return s.size() == i && p.size() == j;
      }
    };
    

Log in to reply
 

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