Draft

题目 题目描述详见：10. 正则表达式匹配 - 力扣（LeetCode） 题解 📝 写在前面 之前的题目，或许我不知道快速的、巧妙的解法，但我可以用笨方法，或者说“朴素”的方法是手搓出来。 但这道题我甚至是思路全无，无从下笔，所以特地来记录一下题解思路。 💡 参考 本文的题解来自官方题解 正如本题题目 ”正则表达式匹配” 所说，这是一个逐步匹配的过程。 我们记字符串 $s$ ，字符规律 $p$ 。对于字符规律 $p$ ，它包含以下几类字符： 普通字符 '.'：匹配任意单个字符 '*'：匹配零个或多个前面的那一个元素 事实上，我们可以进一步分为两类：（1）字符（2）星号。 我们每次从字符串 $p$ 取出一个 字符 或 字符+星号 的组合： 对于 $p$ 中的一个字符，它只能在 $s$ 中匹配一个字符，匹配方法具有唯一性； 对于 p 中字符+星号的组合，它可以在 s 中匹配任意自然数个字符，不具有唯一性。 因此我们可以考虑使用动态规划，对匹配的方案进行枚举。 💡 说明 唯一性？ 关于这里的“唯一性”，指的是匹配方式是否确定。 对于字符+星号的组合，由于星号可以匹配0个或多个元素，因此单纯看这个组合是无法确定匹配方式的。 下面是一个例子，单个字符的匹配是唯一确定的，字符+组合则相反： 模式 面对字符 a 匹配方式 是否唯一 a a 只能匹配这 1 个 a，然后双双后移 ✅ 唯一 . a 只能匹配这 1 个 a，然后双双后移 ✅ 唯一 a* aaa 可以匹配 0 个、1 个、2 个、3 个 a ❌ 不唯一 动态规划？ 可以这样理解，因为 * 带来了分支，我们必须尝试所有的分支，才能知道是否存在一个完美的匹配方案。 ...