通配符匹配
难度:
标签:
题目描述
给你一个输入字符串 (
s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：'?'可以匹配任何单个字符。'*'可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
示例 2：
输入：s = "aa", p = "*" 输出：true 解释：'*' 可以匹配任意字符串。
示例 3：
输入：s = "cb", p = "?a" 输出：false 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
提示：
0 <= s.length, p.length <= 2000s仅由小写英文字母组成p仅由小写英文字母、'?'或'*'组成
代码结果
运行时间: 688 ms, 内存: 128.8 MB
/*
* 思路：
* 由于Java Stream不适合处理复杂的动态规划问题，因此这里使用基本的Java语法来实现。
*/
// 无法使用Java Stream实现复杂的动态规划问题，故使用一般Java实现。解释
方法:
该题解使用动态规划的思路来解决通配符匹配问题。定义状态 dp(i, j) 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否匹配。通过分情况讨论当前字符是否匹配以及 '*' 的处理，递归地计算状态值。为了避免重复计算，使用记忆化搜索将已计算过的状态存储起来。最终的答案即为 dp(0, 0) 的结果。
时间复杂度:
O(mn)
空间复杂度:
O(mn)
代码细节讲解
🦆
在动态规划的方法中，你是如何处理字符串和模式长度为0的情况？即当s和p都为空的情况下，dp(0, 0)应该返回什么值？
▷🦆
对于'*'的处理，为什么选择使用`dp(i+1, j) or dp(i, j+1)`这种方式？这里的逻辑是基于什么考虑？
▷🦆
在动态规划算法中，如何确保不会因为递归调用造成栈溢出？特别是在s和p的长度非常大时。
▷🦆
你提到了使用记忆化搜索来避免重复计算，能否详细说明这种方法如何实现？具体是如何存储和查询之前的计算结果的？
▷相关问题
正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*" 输出：true 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*" 输出：true 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
1 <= s.length <= 201 <= p.length <= 20s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符