题目0044:通配符匹配

题目描述

给定一个字符串(s)和一个字符模式(p),实现一个支持'?'和'*'的通配符匹配。

'?'可以匹配任何单个字符。

'*'可以匹配任意字符串(包括空字符串)。

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

说明:

s可能为空,且只包含从a-z的小写字母。

p可能为空,且只包含从a-z的小写字母,以及字符?和*。

示例1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例5:

输入:
s = "acdcb"
p = "a*c?b"
输出: false

解题技巧

• 方法一:带记忆的递归

这里的第一个想法是递归,是一个较为简单的方法,但是如果输入的字符串过长会导致递归深度很大,因此比较耗时。

• 如果字符串相等p==s,返回 True。
• 如果p=='*',返回True。
• 如果p为空或s为空,返回False。
• 若当前字符匹配,即p[0]==s[0]或p[0]=='?',然后比较下一个字符,返回isMatch(s[1:], p[1:])。
• 如果当前的字符模式是一个星号p[0]=='*',则有两种情况。
• 星号没有匹配字符,因此答案是isMatch(s, p[1:])。
• 星号匹配一个字符或更多字符,因此答案是isMatch(s[1:], p)。
• 若p[0] != s[0],返回False。

这个算法由于时间限制,他没有通过所有的测试用例,因此必须进行优化,以下是可以做到的:

1. 记忆。这是优化递归的标准方法。我们使用(s,p)作为键,使用匹配与不匹配作为布尔值。创建一个记忆的哈希映射。将所有已经检查的(s,p)保留在哈希映射中。这样，如果有任何重复的检查，只需查看哈希表，而不需再次进行计算。
2. 清理输入数据,不管a****bc**cc中有多少个星号,它们都可以简化为a*bc*cc。这样的清理有助于减少递归深度。

算法:

• 清理输入数据用一个星号代替多个星号:p = remove_duplicate_stars(p)。
• 初始化记忆哈希表dp。
• 返回helper函数,用清理后的输入作为参数。
• helper(s,p):
• 如果(s,p)已经计算过存储在dp中,则返回dp中的值。
• 如果字符串相等p == s或p == '*',在dp添加dp[(s, p)] = True。
• 反之如果p或s为空,则dp[(s, p)] = False。
• 反之如果当前字符匹配,即p[0] == s[0]或p[0] == '?',则继续检查下一个字符并dp[(s, p)] = helper(s[1:], p[1:])。
• 反之如果当前字符模式是一个星号p[0] == '*',则有两种情况,要么不匹配字符要么匹配一个或多个，符,则dp[(s, p)] = helper(s, p[1:]) or helper(s, p[1:])。
• 反之如果p[0] != s[0],则dp[(s, p)] = False。
• 返回dp[(s, p)]。

class Solution:
    def remove_duplicate_stars(self, p):
        if p == '':
            return p
        p1 = [p[0],]
        for x in p[1:]:
            if p1[-1] != '*' or p1[-1] == '*' and x != '*':
                p1.append(x)
        return ''.join(p1) 

    def helper(self, s, p):
        dp = self.dp
        if (s, p) in dp:
            return dp[(s, p)]

        if p == s or p == '*':
            dp[(s, p)] = True
        elif p == '' or s == '':
            dp[(s, p)] = False
        elif p[0] == s[0] or p[0] == '?':
            dp[(s, p)] = self.helper(s[1:], p[1:])
        elif p[0] == '*':
            dp[(s, p)] = self.helper(s, p[1:]) or self.helper(s[1:], p)
        else:
            dp[(s, p)] = False

        return dp[(s, p)]

    def isMatch(self, s, p):
        p = self.remove_duplicate_stars(p)
        # memorization hashmap to be used during the recursion
        self.dp = {}
        return self.helper(s, p)

复杂度分析

时间复杂度:最好的情况下$\mathcal{O}(\min(S, P))$,最坏的情况下是$\mathcal{O}(2^{\min(S, P/2)})$。其中$S$和$P$指的是输入字符串和字符模式的长度。最好的情况很明显,让我们估算最坏的情况。最耗时的递归是字符模式上的星号形成树的情况,将执行两个分支helper(s, p[1:])和helper(s[1:], p)。数据清理后字符模式中的最大星树为$P/2$,因此时间复杂度为$\mathcal{O}(2^{\min(S, P/2)})$。

空间复杂度:$\mathcal{O}(2^{\min(S, P/2)})$,用来存储记忆哈希表和递归调用堆栈。

• 方法二:动态规划

上面的递归方法体现了当递归深度大的时候有多耗时,所以我们尝试一些更迭代的方法。

第一种方法中的记忆给出了尝试动态规划的想法。这个问题和编辑距离非常相似,所以我们在这里使用完全相同的方法。

我们的想法是将问题简化为简单的问题,例如,有一个字符串adcebdk和字符模式*a*b?k,计算是否匹配D = True/False。我们将输入字符串和字符模式的长度p_len,s_len和是否匹配D[p_len][s_len]联系起来。

让我们进一步介绍D[p_idx][s_idx],D[p_idx][s_idx]代表的是字符模式中的第p_idx字符和输入字符串的第s_idx字符是否匹配。

如果字符相同或字符模式的字符为?,则

规则1:$D[p_{idx}][s_{idx}] = D[p_{idx} - 1][s_{idx} - 1] \qquad (1)$

如果字符模式的字符为星号且D[p_idx - 1][s_idx - 1] = True,则:

• 星号匹配完成。
• 星号继续匹配更多的字符。

规则2:$D[p_{idx} - 1][i] = \textrm{True}, i \ge s_{idx} - 1 \qquad(2)$

所以,每一步的计算是基于之前完成的计算完成的。

算法:

初始化匹配表为False,除了D[0][0] = True。

使用规则1和规则2计算表格,最后返回D[p_len][s_len]作为答案。

class Solution:
    def isMatch(self, s, p):
        s_len = len(s)
        p_len = len(p)

        # base cases
        if p == s or p == '*':
            return True
        if p == '' or s == '':
            return False

        # init all matrix except [0][0] element as False
        d = [ [False] * (s_len + 1) for _ in range(p_len + 1)]
        d[0][0] = True

        # DP compute 
        for p_idx in range(1, p_len + 1):
            # the current character in the pattern is '*'
            if p[p_idx - 1] == '*':
                s_idx = 1
                # d[p_idx - 1][s_idx - 1] is a string-pattern match 
                # on the previous step, i.e. one character before.
                # Find the first idx in string with the previous math.
                while not d[p_idx - 1][s_idx - 1] and s_idx < s_len + 1:
                    s_idx += 1
                # If (string) matches (pattern), 
                # when (string) matches (pattern)* as well
                d[p_idx][s_idx - 1] = d[p_idx - 1][s_idx - 1]
                # If (string) matches (pattern), 
                # when (string)(whatever_characters) matches (pattern)* as well
                while s_idx < s_len + 1:
                    d[p_idx][s_idx] = True
                    s_idx += 1
            # the current character in the pattern is '?'
            elif p[p_idx - 1] == '?':
                for s_idx in range(1, s_len + 1): 
                    d[p_idx][s_idx] = d[p_idx - 1][s_idx - 1] 
            # the current character in the pattern is not '*' or '?'
            else:
                for s_idx in range(1, s_len + 1): 
                    # Match is possible if there is a previous match
                    # and current characters are the same
                    d[p_idx][s_idx] = \
                    d[p_idx - 1][s_idx - 1] and p[p_idx - 1] == s[s_idx - 1]  

        return d[p_len][s_len]

复杂度分析

时间复杂度:$\mathcal{O}(S P)$,其中$S$和$P$指的是字符模式和输入字符串的长度。

空间复杂度:$\mathcal{O}(S P)$,用来存储匹配表格。

• 方法三:回溯

复杂度$\mathcal{O}(S P)$比$\mathcal{O}(2^{\min(S, P/2)})$好的多,但是仍然有改进的余地。不需要计算整个表格,也就是检查每个星号的所有可能性:

• 匹配0个字符。
• 匹配1个字符。
• 匹配2个字符。
• ...
• 匹配所有剩余的字符。

让我们从匹配0个字符开始,如果这个假设导致不匹配,则回溯:回到前一个星号,假设它匹配一个字符,然后继续。若又是不匹配的情况?再次回溯:回到上一个星号,假设匹配两个字符,等等。

算法:

我们使用两个指针:s_idx遍历输入字符串,p_idx遍历字符模式。当s_idx < s_len:

• 如果字符模式仍有字符p_idx < p_len且指针下的字符匹配p[p_idx] == s[s_idx]或p[p_idx] == '?',则两个指针向前移动。
• 反之如果字符模式仍有字符p_idx < p_len且p[p_idx] == '*',则首先检查匹配0字符的情况,即只增加模式指针p_idx++。记下可能回溯的位置star_idx和当前字符串的位置s_tmp_idx。
• 反之如果出现不匹配的情况:
• 如果字符模式中没有星号,则返回False。
• 如果有星号,则回溯:设置p_idx = star_idx + 1和s_idx = s_tmp_idx + 1,假设这次的星匹配多个字符。则可能的回溯为s_tmp_idx = s_idx。
• 如果字符模式的所有剩余字符都是星号,则返回True。

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        s_len, p_len = len(s), len(p)
        s_idx = p_idx = 0
        star_idx = s_tmp_idx = -1

        while s_idx < s_len:
            # If the pattern caracter = string character
            # or pattern character = '?'
            if p_idx < p_len and p[p_idx] in ['?', s[s_idx]]:
                s_idx += 1
                p_idx += 1
            # If pattern character = '*'
            elif p_idx < p_len and p[p_idx] == '*':
                # Check the situation
                # when '*' matches no characters
                star_idx = p_idx
                s_tmp_idx = s_idx
                p_idx += 1
            # If pattern character != string character
            # or pattern is used up
            # and there was no '*' character in pattern 
            elif star_idx == -1:
                return False
            # If pattern character != string character
            # or pattern is used up
            # and there was '*' character in pattern before
            else:
                # Backtrack: check the situation
                # when '*' matches one more character
                p_idx = star_idx + 1
                s_idx = s_tmp_idx + 1
                s_tmp_idx = s_idx

        # The remaining characters in the pattern should all be '*' characters
        return all(x == '*' for x in p[p_idx:])

复杂度分析

时间复杂度:最好的情况下是$\mathcal{O}(\min(S, P))$,平均情况下是$\mathcal{O}(S \log P)$,其中$S$和$P$指的是字符模式和输入字符串的长度。详细证明可点击:证明过程。

空间复杂度:$\mathcal{O}(1)$。