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

• ``````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];
}``````

• 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];
}``````

• ``````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];
}``````

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