# Regular Expression Matching     ## Intuition

Use dynamic programming to solve this problem.

1. Define a status dp[i][j]. If dp[i][j] == True, s[:i] matches p[:j].

1. The recurrence formular depends on p[j] and p[j + 1].
• If p[j + 1] != '*', dp[i][j] = dp[i - 1][j - 1] and (s[i] == p[j] or p[j] == '.'
• If p[j + 1] == '*',
• If p[j] == '.', dp[i][j + 1] = True if there exists any k where dp[k][j - 1] == True
• If p[j] != '.', dp[i][j + 1] = True if there exists any k where dp[k][j - 1] == True and characters in s[k + 1: i + 1] are all p[j].
2. Then we could use the recurrence formular to solve the problem from down to top.

Here I uses a skill. Since all '*' are only used to match multiple times of an existing character, we could combime it with the previous character and treat them as a single character.

## Solution

``````
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# Pre-format p to generate a list and combine '*' with previous
# character.
pattern = []
index = 0
while index < len(p):
if index + 1 < len(p) and p[index + 1] == '*':
pattern.append(p[index:index + 2])
index += 2
else:
pattern.append(p[index])
index += 1

# Init dp status storage
dp = [[False] * (len(pattern) + 1) for _ in range(len(s) + 1)]
dp = True

# Bottom-up solve dp problem
for i in range(len(s) + 1):
for j in range(1, len(pattern) + 1):
if len(pattern[j - 1]) == 1:
if i > 0:
dp[i][j] = dp[i - 1][j - 1] and (pattern[j - 1] == '.' or s[i - 1] == pattern[j - 1])
else:
if pattern[j - 1] == '.':
dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
else:
dp[i][j] = dp[i][j - 1] or (dp[i - 1][j] and s[i - 1] == pattern[j - 1])

return dp[-1][-1]

``````