16 line DP solution with O(n) space & O(mn) time


  • 1
    L
    function isMatch(s, p) {
      var prev = [];
      var now = [];
      for (var i = 0; i <= s.length; i++) {
        var tmp = prev;
        prev = now;
        now = tmp;
        now[0] = i === 0;
        for (var j = 1; j <= p.length; j++) {
          now[j] = p[j - 1] === '*' ?
            prev[j] || prev[j - 1] || now[j - 1] :
            prev[j - 1] && (s[i - 1] === p[j - 1] || p[j - 1] === '?');
        }
      }
      return !!now[p.length];
    }

  • 0
    L

    Using single array and a tmp variable

    function isMatch(s, p) {
          var prev, now = [];
          for (var i = 0; i <= s.length; i++) {
            prev = now[0];
            now[0] = i === 0;
            for (var j = 1; j <= p.length; j++) {
              var tmp = now[j];
              now[j] = p[j - 1] === '*' ?
                now[j] || prev || now[j - 1] :
                prev && (s[i - 1] === p[j - 1] || p[j - 1] === '?');
              prev = tmp;
            }
          }
          return !!now[p.length];
        }

  • 0
    L
    function isMatch(s, p) {
      for (var i = 0, j, prev, tmp, now = []; i <= s.length; i++)
        for (j = 1, prev = now[0], now[0] = i === 0; j <= p.length; j++) {
          tmp = now[j];
          now[j] = p[j - 1] === '*' ?
            now[j] || prev || now[j - 1] :
            prev && (s[i - 1] === p[j - 1] || p[j - 1] === '?');
          prev = tmp;
        }
      return !!now[p.length];
    }

Log in to reply
 

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