Reduced the space of most top answers from `O(nk)`

to `O(k)`

. (n = length of s, k = length of pattern)

Thinking as if it was a 2D array, the `dp[i][j]`

holds whether the substring `0..i`

of `s`

does match substring `0..j`

of `p`

. So start at `dp[0][0]`

and iterate. At each step update all substring / subpattern pairs that can be reached from current substring / subpattern position. There are only 3 pairs possibly reachable.

When checking a position, you can either consume a char that matches the pattern (exact match or match `.`

) and move both forward.

OR

when pattern is followed by `*`

then you have two options:

- ignore
`x*`

, just go ahead in pattern - consume a char in
`s`

and stay in pattern

```
public boolean isMatch(String s, String p) {
boolean[] pre = new boolean[p.length()+1];
boolean[] next = new boolean[p.length()+1];
pre[0] = true;
for (int sI = 0; sI <= s.length(); sI++) {
for (int pI = 0; pI < p.length(); pI++) {
if (!pre[pI]) continue; // you can't go anywhere from here
if (pI < p.length() - 1 && p.charAt(pI+1) == '*') { // look ahead if pI not at the end
pre[pI+2] |= pre[pI]; // skip x*
if (sI < s.length() && (s.charAt(sI) == p.charAt(pI) || p.charAt(pI) == '.')) {
next[pI] |= pre[pI]; // consume x, stay in pattern
}
} else if (sI < s.length() && (s.charAt(sI) == p.charAt(pI) || p.charAt(pI) == '.')) {
next[pI+1] |= pre[pI]; // consume x, move pattern
}
}
pre = sI == s.length()? pre : next;
next = new boolean[p.length()+1];
}
return pre[p.length()];
}
```