# Regular Expression Matching

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).

```
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0] = True
for j in range(1, n+1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
else:
dp[0][j] = j > 1 and p[j-2] == '*' and dp[0][j-2]
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] == s[i-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = dp[i][j-2] or (p[j-2] == s[i-1] or p[j-2] == '.') and dp[i-1][j]
else:
dp[i][j] = False
return dp[m][n]
```

## Related Problems

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return *the maximum coins you can collect by bursting the balloons wisely*.

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return *its area*.

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.