作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
问题描述
给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。
示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
方法一：动态规划
解题步骤
- 初始化状态数组：创建一个二维布尔数组 ( dp ) ，其中 ( dp[i][j] ) 表示字符串 ( s ) 的前 ( i ) 个字符是否与模式 ( p ) 的前 ( j ) 个字符匹配。
- 处理边界条件：
- ( dp[0][0] = \text{True} )，两个空字符串是可以匹配的。
- ( dp[i][0] = \text{False} )，空模式不能匹配非空字符串。
- ( dp[0][j] )，只有当 ( p ) 的前 ( j ) 个字符全部为 ‘*’ 时才为真。
- 填充状态数组：
- 如果 ( p[j-1] == ‘?’ ) 或 ( s[i-1] == p[j-1] )，则 ( dp[i][j] = dp[i-1][j-1] )。
- 如果 ( p[j-1] == ‘’ )，则 ( dp[i][j] = dp[i][j-1] )（不使用 '’) 或 ( dp[i-1][j] )（使用 ‘*’）。
- 返回结果：( dp[len(s)][len§] )。
python示例
def isMatch(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 - 1] for i in range(1, m + 1): for j in range(1, n + 1): if p[j - 1] == '?' or s[i - 1] == p[j - 1]: dp[i][j] = dp[i - 1][j - 1] elif p[j - 1] == '*': dp[i][j] = dp[i][j - 1] or dp[i - 1][j] return dp[m][n] # 示例调用 print(isMatch("aa", "a")) # 输出: False print(isMatch("aa", "*")) # 输出: True
算法分析
- 时间复杂度：(O(M \times N))，其中 (M) 和 (N) 分别是字符串 (s) 和模式 (p) 的长度。
- 空间复杂度：(O(M \times N))，用于存储状态数组。
方法二：双指针
解题步骤
- 初始化指针：分别为字符串 ( s ) 和模式 ( p ) 设置两个指针 ( i ) 和 ( j )。
- 跟踪最后一个星号：使用变量记录最后匹配的 ‘*’ 的位置和对应的 ( s ) 的指针位置。
- 匹配字符串与模式：
- 如果当前字符匹配或 ( p[j] == ‘?’ )，则 ( i ) 和 ( j ) 都加一。
- 如果 ( p[j] == ‘*’ )，更新星号匹配的位置，将 ( j ) 增加一，并记录 ( i ) 的位置。
- 如果不匹配，检查是否存在之前匹配的 ‘'，如果有，回溯到最后一个 '’，增加对应的 ( s ) 的指针位置。
- 检查剩余模式字符：所有主要字符匹配后，确保模式剩余的都是 ‘*’。
python示例
def isMatch(s: str, p: str) -> bool: si, pi = 0, 0 star_idx = -1 match = 0 while si < len(s): if pi < len(p) and (s[si] == p[pi] or p[pi] == '?'): si += 1 pi += 1 elif pi < len(p) and p[pi] == '*': star_idx = pi match = si pi += 1 elif star_idx != -1: pi = star_idx + 1 match += 1 si = match else: return False while pi < len(p) and p[pi] == '*': pi += 1 return pi == len(p) # 示例调用 print(isMatch("aa", "a")) # 输出: False print(isMatch("aa", "*")) # 输出: True
算法分析
- 时间复杂度：(O(M + N))，其中 (M) 和 (N) 分别是字符串 (s) 和模式 (p) 的长度。在最坏情况下，可能需要回溯，但平均情况下接近线性。
- 空间复杂度：(O(1))，使用常数空间。
方法三：贪心算法
解题步骤
- 初始化指针：与双指针方法类似，使用贪心策略优化处理 ‘*’ 的回溯过程。
- 贪心匹配：使用贪心策略在遇到 ‘*’ 时尽可能地延迟匹配，优先匹配后面的字符。
- 最后检查：确保没有多余的非 ‘*’ 字符在模式 ( p ) 中残留。
python示例
代码结构与方法二相似，主要优化在处理 ‘*’ 的策略上，尽量减少回溯。
def isMatch(s: str, p: str) -> bool: si, pi = 0, 0 star_idx = -1 match = 0 while si < len(s): if pi < len(p) and (s[si] == p[pi] or p[pi] == '?'): si += 1 pi += 1 elif pi < len(p) and p[pi] == '*': star_idx = pi match = si pi += 1 elif star_idx != -1: pi = star_idx + 1 match += 1 si = match else: return False while pi < len(p) and p[pi] == '*': pi += 1 return pi == len(p) # 示例调用 print(isMatch("aa", "a")) # 输出: False print(isMatch("aa", "*")) # 输出: True
算法分析
- 时间复杂度：(O(M + N))，其中 (M) 和 (N) 分别是字符串 (s) 和模式 (p) 的长度。尽管存在回溯机制，但贪心策略尽可能减少不必要的回溯。
- 空间复杂度：(O(1))，只使用了几个辅助变量，不依赖于输入大小。
方法三：贪心算法 (续)
这种方法通过贪心算法优化了处理 ‘’ 的回溯过程，通过在每次遇到 '’ 时，记录当前位置并尝试匹配后续字符，如果后续匹配失败，再回到 ‘*’ 的位置尝试更少的字符匹配，直至找到合适的匹配或确定无法匹配。
python示例
def isMatch(s: str, p: str) -> bool: s_idx, p_idx = 0, 0 # Pointers for string and pattern last_star = -1 # Last position of '*' in p match_idx = 0 # Last position matched in s after a '*' while s_idx < len(s): if p_idx < len(p) and (p[p_idx] == '?' or p[p_idx] == s[s_idx]): s_idx += 1 p_idx += 1 elif p_idx < len(p) and p[p_idx] == '*': last_star = p_idx match_idx = s_idx p_idx += 1 elif last_star != -1: p_idx = last_star + 1 match_idx += 1 s_idx = match_idx else: return False # Check for remaining characters in p while p_idx < len(p) and p[p_idx] == '*': p_idx += 1 return p_idx == len(p) # 示例调用 print(isMatch("adceb", "*a*b")) # 输出: True print(isMatch("acdcb", "a*c?b")) # 输出: False
算法分析
- 时间复杂度：(O(M + N))，主要时间消耗在初次遍历和处理 ‘*’ 后的回溯上。
- 空间复杂度：(O(1))，不需要额外的存储空间，所有操作均在原字符串上进行。
这三种方法各有优势和适用场景。动态规划提供了一种稳定的解决方案，适合大多数情况；双指针方法在空间上更优，适用于内存敏感的环境；而贪心算法尝试在运行时优化性能，特别适合需要频繁处理复杂模式的应用。选择哪种方法取决于具体的应用需求、性能考量和开发资源。
欢迎关注微信公众号 数据分析螺丝钉
