问题描述

给定一文本字符串 std::string s, 以及一个 pattern 串 std::string p, 试判定 s 与 p 是否匹配。

补充说明

假设文本串只被允许包含大小写英文字母，而 pattern 串除了大小写英文字母外还被允许包含字符类符号，在这些字符类符号中，’*’ 代表任意有限长的由大小写英文字母组成的字符串，’?’ 代表任意单个大小写英文字符；

所谓的「s 与 p 匹配」指的是：如果 p 全由大小写英文字母组成，那么 p 和 s 匹配当且仅当表达式 p == s 的求值结果为 true ;

若不然，若 p 中有 ‘*’ 或者 ‘?’ 这样的字符类，则我们说 p 与 s 是匹配的当且仅当能够对 p 中的 ‘*’ 与 ‘?’ 字符进行有限次替换使得 p == s.

对于有正则表达式应用经验的读者来说，’*’ 其实可以看作是「通配符」，能够匹配 0 长字符子串，也能够匹配任意有限长的字符子串，’?’ 也可以看作是通配符，只不过它相比于 ‘*’ 只能够匹配长度为 1 的字符子串。

以 std::string s = "aabca" , std::string p = "a*c?" 举例，我们可以让 p 的 '*' 替换为 "ab" , 再让 '?' 替换为 'a' , 从而将 p 替换为 "aabca" , 从而我们说 p 和 s 是匹配的。

以 std::string s = "cbbc", std::string p = "?**a" 举例，无论我们让 p 中的（两个）’*’ 被替换为何物，让 '?' 被替换何物，都无法从 p 得到 s, 这时我们可以说 p 和 s 是不匹配的。

回溯解法

思想

上述的讨论除了帮助我们更明确地进一步理解问题本身之外，还向我们揭示了一个判定 p 与 s 是否匹配的思路：想象我们是在一个字符一个字符地扫描 p 中的字符（字符类）和 s 中的字符，指针 intptr_t i 指向 s 中正在被扫描到的字符，指针 intptr_t j 指向 p 中正在被扫描到的字符（字符类），若 p[j] 是大小写英文字母，则如果 s[i] == p[j], 就可以让 i, j 都自增，如果 p[j] == '?', 由于 '?' 匹配任何字符，所以也相当于 s[i] == p[j], 也自增 i 和 j, 如果 p[j] == '*', 我们就尝试让这个 '*' 分别匹配不同长度的 s 自 i 开始的 n 长子串，这个 n 可以分别尝试 0 到 N-i.

实现

以下是 C++ 实现：

/**
 * 返回 s 指向的字符串和 p 指向的字符串是否匹配。
 * 
 * 参数说明：
 * 1. s 指向文本串的首字符（如果该文本串非空），或者指向一个值为 0 的地址（代表空串）；
 * 2. p 指向 pattern 串的首字符（如果该 pattern 串非空），或者指向一个值为 0 的地址（代表空 pattern）；
 * 3. i 表示递归调用时当前 s 的首字符偏移量：s[i] 表示文本串的第一个字符（如果有的话）；
 * 4. j 表示递归调用时当前 p 的首字符偏移量：p[j] 表示 pattern 串的第一个字符（如果有的话）；
 * 5. N 表示文本串长度，我们用 i < N 来判断当前文本串是否是非空的；
 * 6. M 表示 pattern 串的长度，我们用 j < M 来判定当前 pattern 串是否是非空的。
 * 
 * 运行结果示例：
 * <https://leetcode.com/submissions/detail/753424879/>
 * 
 * 额外说明：
 * 1. 空 pattern 匹配且只能够匹配空串。
 */
bool isMatchRecursive(char *s, char *p, size_t i, size_t j, size_t N, size_t M) {
    while (j < M) {
        if (p[j] == '*') {
            // 当有连续多个 '*' 时，可以等价地看成只有 1 个 '*', 效果是一样的。
            while (j < M && p[j] == '*')
                ++j;

            // 分别尝试让 '*' 匹配不同长度的 s 中的子串，然后再让剩下的 p 匹配剩下的 s.
            for (size_t n = 0; i+n <= N; ++n)
                if (isMatchRecursive(s, p, i+n, j, N, M))
                    return true;

            // 尝试了让 '*' 分别匹配所有可能长度的子串，余下的 p 都无法匹配余下的 s, 则失败。
            return false;
        } else if (i < N && (p[j] == '?' || s[i] == p[j])) {
            // 匹配单个字符
            ++i;
            ++j;
        } else {
            // 不匹配
            return false;
        }
    }
    
    return i==N && j==M;
}

/** 
 * 返回文本串 s 与 pattern 串 p 是否匹配。
 */
bool isMatch(std::string s, std::string p) {
    return isMatchRecursive(s.data(), p.data(), 0, 0, s.size(), p.size());
}

时间复杂度概览

以下 testcase 能够使得上列代码运行超时（LeetCode 报 TLE 错误）：

char *s = "abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb";
char *p = "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb";

基本上，你可以理解为这样的解法它的时间复杂度是指数级别的。

考虑：