# 2D array solution then evolve to 1D space efficient one

• ``````public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] T = new boolean[s.length() + 1][p.length() + 1];
T[0][0] = true;
for (int i = 2; i < T[0].length; i++) {
if (p.charAt(i - 1) == '*') {
T[0][i] = T[0][i - 2];
}
}
for (int i = 1; i < T.length; i++) {
for (int j = 1; j < T[0].length; j++) {
if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
T[i][j] = T[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
T[i][j] = T[i][j - 2];
if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
T[i][j] = T[i][j] | T[i - 1][j];
}
} else {
T[i][j] = false;
}
}
}
return T[s.length()][p.length()];
}
}
``````

From solution above, we can tell a new T[i][j] depends on last row and current row's values which are T[i-1][j-1], T[i-1][j] and T[i][j-2].
According to that, we can come out space efficient solution below:

``````public class Solution {
public boolean isMatch(String s, String p) {
boolean[] T = new boolean[p.length() + 1];
T[0] = true;
for (int i = 2; i < T.length; i++) {
if (p.charAt(i - 1) == '*') {
T[i] = T[i - 2];
}
}
//leftUp stands for  T[i-1][j-1]
//up stands for T[i-1][j]
//prev2 stands for T[i][j-2]
boolean leftUp, up, prev2;
for (int i = 1; i <= s.length(); i++) {
T[0] = false;
leftUp  = i == 1 ? true : false;
for (int j = 1; j <= p.length(); j++) {
up = T[j];
prev2 = j >= 2? T[j - 2] : false;
if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
T[j] = leftUp;
} else if (p.charAt(j - 1) == '*') {
T[j] = prev2;
if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
T[j] |= up;
}
} else {
T[j] = false;
}
leftUp = up;
}
}
return T[p.length()];
}
}
``````

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