题目描述

判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：

1、'?' 可以匹配任何单个字符；

2、'*' 可以匹配任意字符串（包括空字符串）

两个串完全匹配才算匹配成功。

1<=|s|, |p| <= 1000

s仅包含小写英文字母

p包含小写英文字母，？和 *

---

测试样例

输入:

"aa"

"a"

输出: false

输入:

"aa"

"aa"

输出: true

输入:

"aaa"

"aa"

输出: false

输入:

"aa"

"*"

输出: true

说明: '*' 可以替换任何字符串

输入:

"aa"

"a*"

输出: true

输入:

"ab"

"?*"

输出: true

说明: '?' -> 'a' '*' -> 'b'

输入:

"aab"

"c*a*b"

输出: false

---

解题思路

1、记忆化搜索

每次搜索判断s从i位置开始的后缀和p从j位置开始的后缀可否匹配，使用一个dict来存储搜索方案，这里记为memo，key是(i, j)，value是一个布尔值，这里记为match，代表是否匹配。

在每次搜索前需要先进行3个条件判断，这3个条件判断的顺序尤为重要，不然过不了..

条件i). 首先判断p从j位置开始是否为空，若是且s从i位置开始同时也为空，则返回True，否则为False；

条件ii). 接下来判断(i, j)是否在memo里，若是，直接返回对应的value；

条件iii). 最后一个条件是判断s从i位置开始是否为空，若是，则需要p从j开始的后缀全为'*'，否则就返回False

OK，前置条件判断完，下面是搜索的内容。分两种情况：

i). 若p在j这个位置的字符是‘*’，那么对s在下一个位置i+1和p在当前位置进行搜索 或者 对p在下一个位置j+1和s在当前位置进行搜索，只要两者有其一返回True，则置当前结果为True；

ii). 若p在j这个位置的字符不是'*'，那么若想让当前匹配成功，则需要p在j这个位置的字符为'?‘ 或者 与s在i这个位置的字符相同，同时还需要对p在j+1位置开始与s在i+1位置开始进行搜索且返回True

最后，就是将当前结果存到memo，并返回。

2、dp（动态规划）

dp的代码写起来相对会简洁些，dp[i+1][j+1]代表s的前i个字符能否和p的前j个字符匹配，需要注意的是dp需要的空间是(n+1) x (m+1)，其中n、m分别是s和p的长度，因为需要dp[0][0]对应空字符串的情况，并且置为True。

在给dp赋值的时候，也是分两种情况：

i). 若 p[j] == '*'，则 dp[i+1][j+1] 为 dp[i][j+1] or dp[i+1][j] or dp[i][j]；

ii). 若 p[j] != '*'，那么 dp[i+1][j+1] 为 dp[i][j] and (p[j] == s[i] or p[j] == '?')

最终返回dp[n][m]即为所求。

---

代码

1、记忆化搜索

class Solution:

    """

    @param s: A string

    @param p: A string includes "?" and "*"

    @return: is Match?

    """

    def isMatch(self, s, p):

        return self.helper(s, 0, p, 0, {})

    def helper(self, s, s_idx, p, p_idx, memo):

        """判断s从s_idx开始的后缀和p从p_idx开始的后缀可否匹配"""

        # 注意这个判断条件需要放置在最前面

        # 当p的后缀为空时s的后缀也需要为空

        if not p[p_idx:]:

            return not s[s_idx:]

        if (s_idx, p_idx) in memo:

            return memo[(s_idx, p_idx)]

        # 当s的后缀为空而p的后缀不为空时

        # 则需要p的后缀全是'*'

        if not s[s_idx:]:

            p_set = set(p[p_idx:])

            return len(p_set) == 1 and p_set.pop() == '*'

        # 若p在当前位置是'*'，则可以令s在下一个位置和其在当前位置匹配

        # 或者让其在下一个位置和s在当前位置匹配

        if p[p_idx] == '*':

            match = self.helper(s, s_idx + 1, p, p_idx, memo) or \

                self.helper(s, s_idx, p, p_idx + 1, memo)

        # 若p在当前位置不是'*'，则需要p和s的当前字符相同

        # 或者p在当前位置是'?'，同时还需要两者的后缀匹配

        else:

            match = p[p_idx] in (s[s_idx], '?') and \

                self.helper(s, s_idx + 1, p, p_idx + 1, memo)

        memo[(s_idx, p_idx)] = match

        return match

2、dp（动态规划）

class Solution:

    """

    @param s: A string

    @param p: A string includes "?" and "*"

    @return: is Match?

    """

    def isMatch(self, s, p):

        n, m = len(s), len(p)

        # dp[i+1][j+1]：s的前i个字符能否和p的前j个字符匹配

        # 比字符串长度多1，dp[0][0]对应空字符串的情况

        dp = [[False] * (m + 1) for _ in range(n + 1)]

        dp[0][0] = True

        for j in range(1, m + 1):

            dp[0][j] = dp[0][j - 1] and p[j - 1] == '*'

        for i in range(n):

            for j in range(m):

                if p[j] == '*':

                    dp[i + 1][j + 1] = dp[i][j] or dp[i + 1][j] or dp[i][j + 1]

                else:

                    dp[i + 1][j + 1] = dp[i][j] and p[j] in (s[i], '?')

        return dp[n][m]