# Short Java O(k) space DP solution beats 99,5%

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

• @A1m Nice and elegant solution. One question though, what's the meaning of the following two lines?
pre = sI == s.length()? pre : next;
next = new boolean[p.length()+1];
I don't quite follow. Hope you could explain, thank you!

• Each line you are progressing your 2 arrays to the next level by setting prev to next and init an empty next.

The `sI == s.length()?` check is just there for the very last iteration, you can't throw away your pre, since the result is `pre[p.length()];`

Notice that for the very last iteration, only things in pre change cause of that condition `sI < s.length() &&`. `next` is just empty in the last iteration.

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