正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符；
• '*' 匹配零个或多个前面的那一个元素。

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

约定

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *。
• 每次出现 * 时，前面保证是一个合法字符。

输入

• s：待匹配字符串，长度 0 ~ 20
• p：正则表达式串，长度 0 ~ 30

输出

布尔值：s 是否被 p 完全匹配。

示例一

输入：

s = "aa", p = "a"

输出：

false

示例二

输入：

s = "aa", p = "a*"

输出：

true

示例三

输入：

s = "ab", p = ".*"

输出：

true

示例四

输入：

s = "aab", p = "c*a*b"

输出：

true

复杂度要求

• 时间复杂度：O(m·n)
• 空间复杂度：O(m·n)