Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
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
Constraints:
1 <= s.length <= 20
1 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
ac
class Solution {
public boolean isMatch(String s, String p) {
// edge cases
if (s == null || p == null) return false;
// initialize
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int i = 2; i < dp[0].length; i++) {
if (p.charAt(i-1) == '*') {
dp[0][i] = dp[0][i-2];
}
}
// walk, transform function
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.') {
dp[i][j] = dp[i-1][j-1];
}
if (p.charAt(j-1) == '*') {
if (p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != '.') {
dp[i][j] = dp[i][j-2];
} else {
dp[i][j] = (dp[i-1][j] || dp[i][j-1] || dp[i][j-2]);
}
}
}
}
// result
return dp[s.length()][p.length()];
}
}
/*
state: dp[i][j], s.substring(0, i) and p.substring(0, j) is match
function:
1. if p.charAt(j-1) == s.charAt(i-1) , dp[i][j] = dp[i-1][j-1];
2. if p.charAt(j-1) == '.' , dp[i][j] = dp[i-1][j-1];
3. if p.charAt(j-1) == '*' :
(1) if p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != '.', dp[i][j] = dp[i][j-2] // a* means zero a
(2) if p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.':
1) dp[i][j] = dp[i-1][j] // a* means multiple a
2) dp[i][j] = dp[i][j-1] // a* means single a
3) dp[i][j] = dp[i][j-2] // a* means zero a
initialize: dp[0][0] = true;
result: dp[s.length()][p.length()]
*/