华为od机试真题-增强的strstr

### 华为OD机试增强版 `strstr` 函数 #### 题目描述 给定两个字符串 `haystack` 和 `needle`，其中 `needle` 可能包含通配符字符 `'?'` 或者 `'*'`。任务是在 `haystack` 中查找第一个匹配 `needle` 的子串的位置。如果找不到，则返回 `-1`。通配符解释如下： - `'?'` 匹配任意单个字符。 - `'*'` 匹配零个或多个前面的字符。 此问题是对经典 `strstr` 函数的一种扩展版本[^1]。 #### 解决方案概述 为了处理带有通配符模式匹配的问题，通常采用动态规划 (DP) 方法来解决这个问题。通过构建二维 DP 表格，可以有效地追踪到目前为止的最佳匹配状态。对于每一个可能的状态转移情况都进行了详细的考虑，从而确保算法能够覆盖所有的边界条件和特殊情况[^2]。 #### 动态规划解法详解 定义一个布尔类型的二维数组 `dp[i][j]` 来表示前 i 个字符组成的 haystack 是否与前 j 个字符构成的 needle 相匹配。初始化时设置 dp[0][0]=true, 因为空字符串总是相互匹配；另外当 needle 开头有 '*' 符号时也应设为 true，因为 * 能够代表空序列。 遍历过程中依据当前字符的不同采取不同策略更新表格： - 如果两者相等或者 needle[j]=='?', 则继承上一步的结果即 dp[i][j]=dp[i−1][j−1]. - 当遇到 '*' 时需分两种情形讨论：一是将其视作空白不消耗任何字符(dp[i][j]=dp[i][j−1])；二是利用它去尝试匹配尽可能多相同字符直到无法继续为止(dp[i][j]|=dp[i−k][j−1], k∈[1,i]). 最终答案取决于最后一个单元格 dp[m][n] 的真假值以及具体位置索引计算得出。 下面是 Python 实现代码片段: ```python def enhanced_strstr(haystack: str, needle: str) -> int: m, n = len(haystack), len(needle) # Initialize the DP table with False values. dp = [[False] * (n + 1) for _ in range(m + 1)] # Empty pattern matches empty text. dp[0][0] = True # Handle patterns like '*a*b*c*' where leading stars can match zero characters. for j in range(1, n + 1): if needle[j - 1] != '*': break dp[0][j] = True for i in range(1, m + 1): for j in range(1, n + 1): if needle[j - 1] == '?' or needle[j - 1] == haystack[i - 1]: dp[i][j] |= dp[i - 1][j - 1] elif needle[j - 1] == '*': dp[i][j] |= dp[i - 1][j] | dp[i][j - 1] if not dp[-1][-1]: return -1 pos = m for i in reversed(range(n)): if needle[i] == '*': continue pos -= 1 while pos >= 0 and (needle[i] != '?' and needle[i] != haystack[pos]): pos -= 1 return pos if pos < m else -1 ``` 该解决方案的时间复杂度主要由两部分组成：预处理阶段 O(M*N)，实际定位起始点的过程最多也是线性的 O(M+N)[^3].