0044. Wildcard Matching ======================= 题目信息 -------- :题号: 0044. 通配符匹配 :难度: Hard :主题: 字符串、递归、记忆化搜索、动态规划 :原题: `LeetCode 0044 `_ :重点: 从星号长度枚举产生的重复状态,推导到二维前缀状态,并按依赖方向压缩为一维数组 题目重述 -------- 给定字符串 ``s`` 和模式 ``p``,判断模式能否匹配整个字符串。 模式中的字符具有以下含义: * 普通小写字母只能匹配相同字母; * ``?`` 恰好匹配任意一个字符; * ``*`` 可以匹配任意长度的字符序列,包括空序列。 只有字符串和模式都被完整消费时才算匹配成功,不能只匹配字符串中的某个子串。 ``s`` 和 ``p`` 的长度均位于 ``[0, 2000]``。``s`` 只含小写英文字母,``p`` 只含小写英文字母、``?`` 和 ``*``。 自建示例 -------- 星号匹配多个字符: .. code-block:: text 输入:s = "cabxy", p = "c*?y" 输出:true 解释:c 匹配 c,* 匹配 "ab",? 匹配 x,y 匹配 y。 星号匹配空串: .. code-block:: text 输入:s = "ab", p = "a*b" 输出:true 解释:* 可以不消费任何字符。 模式仍有字符未消费: .. code-block:: text 输入:s = "abcd", p = "a*d?" 输出:false 解释:d 匹配字符串末位后,模式中的 ? 已经没有字符可以匹配。 空字符串边界: .. code-block:: text 输入:s = "", p = "***" 输出:true 解释:每个 * 都取空串;若模式中含普通字符或 ?,结果则为 false。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool backtrack( const std::string& s, const std::string& p, int stringIndex, int patternIndex ) { if (patternIndex == static_cast(p.size())) { return stringIndex == static_cast(s.size()); } if (p[patternIndex] == '*') { const bool matchEmpty = backtrack( s, p, stringIndex, patternIndex + 1 ); const bool matchOneMore = stringIndex < static_cast(s.size()) && backtrack(s, p, stringIndex + 1, patternIndex); return matchEmpty || matchOneMore; } if (stringIndex == static_cast(s.size())) { return false; } if (p[patternIndex] != '?' && p[patternIndex] != s[stringIndex]) { return false; } return backtrack(s, p, stringIndex + 1, patternIndex + 1); } bool plainRecursive(const std::string& s, const std::string& p) { return backtrack(s, p, 0, 0); } bool memoDfs( const std::string& s, const std::string& p, int stringIndex, int patternIndex, std::vector>& memo ) { int& cached = memo[stringIndex][patternIndex]; if (cached != -1) { return cached == 1; } bool answer = false; if (patternIndex == static_cast(p.size())) { answer = stringIndex == static_cast(s.size()); } else if (p[patternIndex] == '*') { answer = memoDfs( s, p, stringIndex, patternIndex + 1, memo ); if (!answer && stringIndex < static_cast(s.size())) { answer = memoDfs( s, p, stringIndex + 1, patternIndex, memo ); } } else if ( stringIndex < static_cast(s.size()) && (p[patternIndex] == '?' || p[patternIndex] == s[stringIndex]) ) { answer = memoDfs( s, p, stringIndex + 1, patternIndex + 1, memo ); } cached = answer ? 1 : 0; return answer; } bool memoizedSearch(const std::string& s, const std::string& p) { std::vector> memo( s.size() + 1, std::vector(p.size() + 1, -1) ); return memoDfs(s, p, 0, 0, memo); } bool twoDimensionalDp(const std::string& s, const std::string& p) { const int stringLength = static_cast(s.size()); const int patternLength = static_cast(p.size()); std::vector> dp( stringLength + 1, std::vector(patternLength + 1, false) ); dp[0][0] = true; for (int patternSize = 1; patternSize <= patternLength; ++patternSize) { if (p[patternSize - 1] == '*') { dp[0][patternSize] = dp[0][patternSize - 1]; } } for (int stringSize = 1; stringSize <= stringLength; ++stringSize) { for (int patternSize = 1; patternSize <= patternLength; ++patternSize) { const char patternChar = p[patternSize - 1]; if (patternChar == '*') { dp[stringSize][patternSize] = dp[stringSize][patternSize - 1] || dp[stringSize - 1][patternSize]; } else if ( patternChar == '?' || patternChar == s[stringSize - 1] ) { dp[stringSize][patternSize] = dp[stringSize - 1][patternSize - 1]; } } } return dp[stringLength][patternLength]; } bool oneDimensionalDp(const std::string& s, const std::string& p) { const int patternLength = static_cast(p.size()); std::vector dp(patternLength + 1, false); dp[0] = true; for (int patternSize = 1; patternSize <= patternLength; ++patternSize) { dp[patternSize] = p[patternSize - 1] == '*' && dp[patternSize - 1]; } for (char stringChar : s) { char diagonal = dp[0]; dp[0] = false; for (int patternSize = 1; patternSize <= patternLength; ++patternSize) { const char above = dp[patternSize]; const char patternChar = p[patternSize - 1]; if (patternChar == '*') { dp[patternSize] = dp[patternSize] || dp[patternSize - 1]; } else { dp[patternSize] = diagonal && (patternChar == '?' || patternChar == stringChar); } diagonal = above; } } return dp[patternLength]; } public: bool isMatch(std::string s, std::string p) { return oneDimensionalDp(s, p); } }; 题解 ---- 后缀递归状态 ~~~~~~~~~~~~ 令 ``match(i, j)`` 表示字符串后缀 ``s[i:]`` 能否与模式后缀 ``p[j:]`` 完整匹配。模式已经结束时,只有字符串也 恰好结束才能返回真。 普通字符和 ``?`` 都必须消费一个字符串字符,并把两个下标同时加一。普通字符还要求两者相等;若字符串已经结束, 这两类模式字符都无法继续匹配。 星号分支 ~~~~~~~~ ``*`` 的匹配长度未知,但所有长度都能由两个动作组成: .. code-block:: text match(i, j + 1) 当前 * 匹配空串 match(i + 1, j) 当前 * 再匹配一个字符 第二个动作保留模式下标 ``j``,因此可以连续发生,覆盖 ``*`` 匹配一个、两个或更多字符。任意合法匹配中的当前 ``*`` 要么长度为零,要么至少消费一个字符,所以两个分支覆盖全部可能;每个动作也都严格遵守通配符语义。 重复状态 ~~~~~~~~ 不同星号之间可以用多种方式分配字符,却重新到达同一对下标 ``(i, j)``。直接递归会重复展开相同后缀搜索树,最坏 呈指数增长。 状态只由两个下标决定,总数至多为 ``(m + 1)(n + 1)``。``memoizedSearch`` 缓存每个状态的真假结果,使每个 ``match(i, j)`` 至多求解一次,将时间降为 ``O(mn)``。 前缀动态规划 ~~~~~~~~~~~~ 把同一状态图改为自底向上计算: .. code-block:: text dp[i][j] = s 的前 i 个字符能否与 p 的前 j 个字符完整匹配 ``dp[0][0]`` 为真。普通字符或 ``?`` 匹配当前字符后,剩余问题就是两个前缀都去掉末位: .. code-block:: text dp[i][j] = dp[i - 1][j - 1] 前提是 ``p[j - 1]`` 为 ``?``,或它等于 ``s[i - 1]``。 对于 ``*``,递归中的两个动作直接变为两个前缀状态: .. code-block:: text dp[i][j - 1] * 匹配空串 dp[i - 1][j] * 匹配当前字符,并继续保留使用权 因此: .. code-block:: text dp[i][j] = dp[i][j - 1] || dp[i - 1][j] 第二项可以沿同一列向下传播,使一个星号匹配任意多个字符。最终答案是 ``dp[m][n]``,因为只有该状态同时消费完整 字符串与完整模式。 边界初始化 ~~~~~~~~~~ 空模式只能匹配空字符串,所以 ``dp[i][0]`` 在 ``i > 0`` 时均为假。空字符串只能由模式前缀中的全部星号匹配: .. code-block:: text dp[0][j] = dp[0][j - 1] && p[j - 1] == '*' 连续星号无需合并,真值会在第一行逐个向右传播。若模式前缀中出现普通字符或 ``?``,后续状态都保持为假。 这组初始化也自然覆盖两个边界:``s`` 为空时直接读取第一行末端;``p`` 为空而 ``s`` 非空时,第一列始终为假。 一维压缩 ~~~~~~~~ 二维转移只依赖三个方向:当前行左侧、上一行同列和上一行左上角。用一维数组从左向右更新时: * 更新前的 ``dp[j]`` 是上一行同列; * 更新后的 ``dp[j - 1]`` 是当前行左侧; * ``diagonal`` 保存上一行左上角。 于是星号使用 ``dp[j] || dp[j - 1]``,普通字符与 ``?`` 使用 ``diagonal``。更新当前格之前先保存原 ``dp[j]``,再把它交给下一列作为新的 ``diagonal``。 从左向右的顺序不能颠倒:星号转移需要当前行已经计算出的左侧状态;若从右向左更新,``dp[j - 1]`` 仍属于上一行。 每处理一个字符串字符,还要把 ``dp[0]`` 设为假,因为非空字符串不能由空模式匹配。 状态演化 ~~~~~~~~ 对 ``s = "ab"``、``p = "*?b"``,数组下标表示模式前缀长度: .. list-table:: :header-rows: 1 * - 已处理字符串前缀 - ``dp[0]`` - ``dp[1]``:``*`` - ``dp[2]``:``*?`` - ``dp[3]``:``*?b`` * - ``""`` - 真 - 真 - 假 - 假 * - ``"a"`` - 假 - 真 - 真 - 假 * - ``"ab"`` - 假 - 真 - 真 - 真 第一行中星号匹配空串。处理 ``a`` 后,``?`` 从左上角真值转移;处理 ``b`` 后,末尾普通字符再次从左上角转移, 最终右下角为真。 代码演进 ~~~~~~~~ ``plainRecursive`` 直接枚举星号匹配空串或继续吞字符,完整表达匹配语义,但反复计算相同下标状态。 ``memoizedSearch`` 保存后缀状态,将搜索树压缩为有限状态图。``twoDimensionalDp`` 改用前缀状态,自底向上计算同一组 依赖关系。``oneDimensionalDp`` 再利用每格只依赖三个方向,将表格压缩为一行;公开入口采用该方法。 复杂度分析 ~~~~~~~~~~ 设字符串长度为 ``m``,模式长度为 ``n``。 * 直接递归最坏会反复分配星号长度,时间呈指数增长,递归深度为 ``O(m + n)``; * 记忆化搜索访问至多 ``(m + 1)(n + 1)`` 个状态,时间和缓存空间均为 ``O(mn)``; * 二维动态规划时间为 ``O(mn)``,表格空间为 ``O(mn)``; * 一维动态规划仍执行相同数量的转移,时间为 ``O(mn)``,额外空间降为 ``O(n)``。