前言

终于完成了微软的所有面试，安心等待面试结果了。

AA 面遇到一个字符串匹配的问题，闫神算法基础课中的动态规划部分给了很大的启发，所以将思路写出来给大家分享下，也是作为课程的反馈吧，十分感谢。

注意：算法并没有经过完整的样例测试，可能存在一些细节问题，请见谅。

问题描述

给定一个字符串和一个包含通配符 * 和 ? 的模版，判断给定的模版和字符串是否是可匹配的。其中 * 可以匹配 0 个或任意多个字符，? 可以匹配 0 个或 1 个字符。

样例：

text = "readme.txt"
pattern = "r*e.t?t"

此时：
* ==> "eadm"
? ==> "x"
所以字符串和模版是可匹配的，返回 True

问题分析

首先分析 corner case ：

1. 字符串和模版都为空，直接返回 True ；
2. 字符串和模版存在一个为空，另一个不为空，直接返回 False 。

剩下就是考虑字符串和模版都不为空的情况，可以发现字符串的匹配是无后效性的，即如果当前字符串子串和模版子串是匹配的，后续的字符并不会影响这两个子串的匹配情况。因此，我们可以采用动态规划来对问题进行求解，dp[i][j] 表示以模版的第 i 个字符结尾，以字符串的第 j 个字符结尾的两个子字符串是否匹配，则一共有三种情况：

1. pattern[i] == text[j] ，此时 dp[i][j] = dp[i-1][j-1] ；
2. pattern[i] == "?" ，此时可以匹配 0 或 1 个字符， dp[i][j] = dp[i-1][j] or dp[i-1][j-1]
3. pattern[i] == "*" ，此时可以匹配 0 或任意多个字符，则有 dp[i][j] = dp[i-1][j] or dp[i-1][j-1] or ... dp[i-1][0]

这里为了省去画图的麻烦，就不用闫神那种集合划分的来解释了。

问题求解

Python 版本

def match(text, pattern):
    if not text and not pattern:
        return True
    elif not text or not pattern:
        return False
    else:
        n = len(text)
        m = len(pattern)
        text = "0" + text
        pattern = "0" + pattern
        dp = [[False] * (n+1) for i in range(m+1)]
        dp[0][0] = True
        for i in range(1, m+1):
            for j in range(1, n+1):
                if pattern[i] == text[j]:
                    dp[i][j] = dp[i-1][j-1]
                elif pattern[i] == "?":
                    # 匹配 0 或 1 个字符
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-1]
                elif pattern[i] == "*":
                    dp[i][j] = dp[i-1][j]  # 匹配 0 个字符
                    for k in range(j, -1, -1):
                        dp[i][j] = dp[i][j] or dp[i-1][k]  # 匹配多个字符
        return dp[m][n]

if __name__ == "__main__":
    text = "readme.txt"
    pattern = "r*e.t?t"
    print(match(text, pattern))

求解优化

由于 dp 中任意的状态都仅与上一层的一侧的状态有关，所以可以对上述问题进行空间压缩，优化后的代码如下：

def match2(text, pattern):
    if not text and not pattern:
        return True
    elif not text or not pattern:
        return False
    else:
        n = len(text)
        m = len(pattern)
        text = "0" + text
        pattern = "0" + pattern
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(1, m+1):
            for j in range(n, -1, -1):
                if pattern[i] == text[j]:
                    dp[j] = dp[j-1]
                elif pattern[i] == "?":
                    dp[j] = dp[j] or dp[j-1]
                elif pattern[i] == "*":
                    for k in range(j, -1, -1):
                        dp[j] = dp[j] or dp[k]
        return dp[n]

------------------------------------许愿分割线------------------------------------------------
最后求一波微软的 offer ....