# Reqular Expression Matching

One solution to this problem is applying dynamic programming method. Let dp[i][j] stands for if parttern p[0..j - 1] is matching with s[0..i - 1]. At first dp[0][0] will be true. The iteration formular is:

1. If p[j - 1] match s[i - 1] and dp[i - 1][j - 1] are true, then dp[i][j] are true
2. If p[j - 1] == '*' and p[j - 2] match s[i - 1], dp[i][j] will be true when dp[i - 1][j] is true.
3. If p[j - 1] == '*' and p[0..j - 3] has already been matching with s[0..i - 1] then we can get dp[i][j] is true as the character before * can appears zero time.

After compressed, the dp matrix can just be reduced to two arrays.

public class Solution {
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();

if (m == 0 && n == 0) return true;

boolean[] last = new boolean[m + 1];
boolean[] cur = new boolean[m + 1];

// i = 0;
last[0] = true;
for (int j = 1; j <= m; j++) {
if (j >= 2 && p.charAt(j - 1) == '*') {
last[j] = last[j - 2];
}
}

// i = 1 to n
for (int i = 1; i <= n; i++) {
cur[0] = false;

for (int j = 1; j <= m; j++) {
cur[j] = false;

if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
cur[j] = last[j - 1];
}

if (p.charAt(j - 1) == '*') {
cur[j] |= cur[j - 2];

if (j >= 2 && (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.')) {
cur[j] |= last[j];
}
}
}

boolean[] temp = last;
last = cur;
cur = temp;
}

return last[m];
}
}