Regular Expression Matching

You are given two strings s and p.

The string p represents a pattern and may contain the special characters . and * where:

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

Your task is to determine if the string s matches the pattern p in its entirety.

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

Note: The pattern is guaranteed to be valid. Ensure you use dynamic programming or another efficient approach to pass the test cases.

LaTeX formula: The recurrence can be written as: $$dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } p_j = s_i \text{ or } p_j = '.' \\ dp[i][j-2] \text{ or } (dp[i-1][j] \text{ if } p_{j-1} = s_i \text{ or } p_{j-1} = '.') & \text{if } p_j = '*' \end{cases}$$

inputFormat

The input consists of two lines:

1. The first line contains the string s.
2. The second line contains the pattern p.

Both strings are non-empty and consist of lowercase letters and the characters . and * (only in the pattern).

outputFormat

Output a single line: True if s matches the pattern p, otherwise False.

## sample

aab
c*a*b

True

</p>