Posted on

## Description

Given an input string (`s`) and a pattern (`p`), implement regular expression matching with support for `'.'` and `'*'`.

```'.' Matches any single character.
'*' Matches zero or more of the preceding element.
```

The matching should cover the entire input string (not partial).

Note:

• `s` could be empty and contains only lowercase letters `a-z`.
• `p` could be empty and contains only lowercase letters `a-z`, and characters like `.` or `*`.

Example 1:

```Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
```

Example 2:

```Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
```

Example 3:

```Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
```

Example 4:

```Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
```

Example 5:

```Input:
s = "mississippi"
p = "mis*is*p*."
Output: false```

## Submission

For this problem, we firstly only think about the case where there is only ‘a-z’ and ‘.'(dot). That’s a quite simple problem. There is only one special case, we can match the dot with any one of the letters a-z, and this can be easily recursively implemented.

Now with the ‘*’, every time we check a pattern, we have to check the 0th and 1st letters of the pattern. In a recursive manner, a pattern like “a*” or “.*” can either be “”(empty string) or a letter repeating itself as many times as it can. So we can write this as simple as return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p).

Following is my first submission,

```class Solution {
public boolean isMatch(String s, String p) {
if(s.length() == 0 && p.length() == 0) {
return true;
}

if(p.length() > 0 && p.charAt(0) == '.') {
if(p.length() > 1 && p.charAt(1) == '*') {
if(s.length() > 0) {
return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p);
}
return isMatch(s, p.substring(2));
}
if(s.length() > 0) {
return isMatch(s.substring(1), p.substring(1));
}
}

if(p.length() > 0 && p.charAt(0) <= 'z' && p.charAt(0) >= 'a') {
if(p.length() > 1 && p.charAt(1) == '*') {
if(s.length() > 0 && s.charAt(0) == p.charAt(0))
return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p);
return isMatch(s, p.substring(2));
} else if (s.length() > 0 && p.charAt(0) == s.charAt(0)) {
return isMatch(s.substring(1), p.substring(1));
}
}

return false;
}
}```

But as we may find, the function isMatch is called many times and obviously, for a function call isMatch(m, n), a same pair of m and n may be called several times during the execution. To reduce that redundancy, we can store the result of each execution result in a hash map {(int s.length(), int p.length()): boolean result}, or in implementation, an array. For the same pair of string and pattern, the remaining length of the string and pattern can uniquely index them and the final space cost will be O(N^2).

With some modifications based on the previous submission, we can write the dynamic programming program as the following. Since we have to know if a result is already calculated and stored, we need 3 states, in addition to true and false. For the primitive boolean, there are only 2 states. To solve this problem, we use an enum type Result, which contains TRUE and FALSE. If an enum Result type variable is only declared without definition, its state is null.

```enum Result {
TRUE, FALSE
}

class Solution {
Result[][] res;

public boolean isMatch(String s, String p) {
int longer = s.length() > p.length()? s.length() : p.length();
res = new Result[longer + 1][longer  +1];
return isMatchUtil(s, p) == Result.TRUE ? true : false;
}

public Result isMatchUtil(String s, String p) {
if(res[s.length()][p.length()] != null) return res[s.length()][p.length()];

if(s.length() == 0 && p.length() == 0) {
return res[0][0] = Result.TRUE;
}

if(p.length() > 0 && p.charAt(0) == '.') {
if(p.length() > 1 && p.charAt(1) == '*') {
if(s.length() > 0) {
return ((res[s.length()][p.length() - 2] = isMatchUtil(s, p.substring(2))) == Result.TRUE
|| (res[s.length() - 1][p.length()] = isMatchUtil(s.substring(1), p)) == Result.TRUE) ? Result.TRUE : Result.FALSE;
}
return res[s.length()][p.length() - 2] = isMatchUtil(s, p.substring(2));
}
if(s.length() > 0) {
return res[s.length() - 1][p.length() - 1] = isMatchUtil(s.substring(1), p.substring(1));
}
}

if(p.length() > 0 && p.charAt(0) <= 'z' && p.charAt(0) >= 'a') {
if(p.length() > 1 && p.charAt(1) == '*') {
if(s.length() > 0 && s.charAt(0) == p.charAt(0))
return ((res[s.length()][p.length() - 2] = isMatchUtil(s, p.substring(2))) == Result.TRUE
|| (res[s.length() - 1][p.length()] = isMatchUtil(s.substring(1), p)) == Result.TRUE) ? Result.TRUE : Result.FALSE;
return res[s.length()][p.length() - 2] = isMatchUtil(s, p.substring(2));
} else if (s.length() > 0 && p.charAt(0) == s.charAt(0)) {
return res[s.length() - 1][p.length() - 1] = isMatchUtil(s.substring(1), p.substring(1));
}
}

return Result.FALSE;
}
}```

## Solution

```enum Result {
TRUE, FALSE
}

class Solution {
Result[][] memo;

public boolean isMatch(String text, String pattern) {
memo = new Result[text.length() + 1][pattern.length() + 1];
return dp(0, 0, text, pattern);
}

public boolean dp(int i, int j, String text, String pattern) {
if (memo[i][j] != null) {
return memo[i][j] == Result.TRUE;
}
boolean ans;
if (j == pattern.length()){
ans = i == text.length();
} else{
boolean first_match = (i < text.length() &&
(pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));

if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
ans = (dp(i, j+2, text, pattern) ||
first_match && dp(i+1, j, text, pattern));
} else {
ans = first_match && dp(i+1, j+1, text, pattern);
}
}
memo[i][j] = ans ? Result.TRUE : Result.FALSE;
return ans;
}
}```