Skip to main content

44. 通配符匹配 [hard]

44. 通配符匹配 [hard]​

https://leetcode-cn.com/problems/wildcard-matching/

给定一个字符串 (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

通过次数31,335 | 提交次数112,551

Second Try (time exceeded version)​

  • 复制题解的版本进行调试

还是不太爽啊，最后还是不跟主流思路一样了，毕竟考虑思路不太一样，还是走递归吧

虽然按递归写法通过了，但是看评论和题解大家都写成动态规划这个版本，但我却没有这条思路，想要看看自己怎么就跟大流不一样。但是因为一直无法理解dp[i][j]=dp[i-1][j]||dp[i][j-1];，思考了几个小时，还是来测试一波比较妥当。

遇到*号的正常理解的是: dp[i][j]取决于dp[i][j-1]和dp[i-1][j-1]，前者直接把*当作空字符串来比较（j-1不加入比较），后者对应把pattern当作一个字符，消耗一个string和一个pattern。

但是有一点没考虑到，如果string[i-1]本身也是被pattern[j]的""号消耗掉的，d[i-1][j-1]是无法被匹配的(因为j-1已经不再是``号)，但是d[i-1][j]倒是被匹配。

所以需要写成dp[i][j]=dp[i-1][j]||dp[i][j-1];;同时这个动态写法，还需要考虑到当string为0而pattern不为0的情况，这里只有*号比较号理解，只要后面都是*号就可以（总感觉还是不需要这一步，毕竟刚开始没有什么可以用来判断cache为True的）

对于初始条件，也很麻烦，这是因为循环里面并没有经过i=0或是j=0的阶段，因此需要额外进行考虑。

//dp[0][1]~dp[0][p.length]只有p的j字符以及前面所有字符都为'*'才为true
for (int j=1;j<=plen;j++)dp[0][j]=p.charAt(j-1)=='*'&&dp[0][j-1];
class Solution {
    // 题解修改
    public void print(boolean[][] m) {
        for (boolean[] arr : m) {
            System.out.print("[ ");
            for (boolean a : arr) {
                System.out.printf("%-6s", a );
            }
            System.out.print("]\t");
        }
        System.out.println();
    }
    public boolean isMatch(String s, String p) {
        if (p==null||p.isEmpty())return s==null||s.isEmpty();
        int slen = s.length(),plen=p.length();
        boolean[][] dp=new boolean[slen+1][plen+1];
        //初始化dp数组,dp[1][0]~dp[s.length][0]默认值flase不需要显式初始化为false
        dp[0][0]=true;
        //dp[0][1]~dp[0][p.length]只有p的j字符以及前面所有字符都为'*'才为true
        for (int j=1;j<=plen;j++)dp[0][j]=p.charAt(j-1)=='*'&&dp[0][j-1];
        print(dp);
        //填写dp数组剩余部分
        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= plen; j++) {
                char si = s.charAt(i - 1),pj=p.charAt(j-1);
                if (si==pj||pj=='?'){
                    dp[i][j]=dp[i-1][j-1];
                }else if (pj=='*'){
                    // 如果修改为 dp[i][j]=dp[i-1][j-1]||dp[i][j-1];则无法通过判断 "adceb" "*a*b"
                    if ((dp[i-1][j-1]||dp[i][j-1]) != (dp[i-1][j]||dp[i][j-1])){
                        System.out.printf("%d %d %b %b ", i, j, dp[i-1][j-1], dp[i-1][j]);
                        print(dp);
                        break;
                    }
                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                }
            }
        }
        print(dp);
        return dp[slen][plen];
    }
"acdb"
"*a*b"

输出
false

预期结果
true

stdout
[ true  true  false false false ]   [ false false false false false ]   [ false false false false false ]   [ false false false false false ]   [ false false false false false ]   
2 1 false true [ true  true  false false false ]    [ false true  true  true  false ]   [ false false false false false ]   [ false false false false false ]   [ false false false false false ]   
[ true  true  false false false ]   [ false true  true  true  false ]   [ false false false false false ]   [ false false false false false ]   [ false false false false false ]

First Try​

2020-06-16

遇到*的时候，需要考虑 i到n位置的所有可能

  • *可以直接被跳过去，仅消耗p本身
  • *可以不被跳过去，消耗任意长度的s字符串，并进行遍历
  • 当p被消耗完的时候，s必须得被消耗完；当s被消耗完的时候，需要继续进行检查处理

需要使用两种方法进行时间压缩，一是使用缓存，二是对无限背包问题的压缩

当遇到一个*号的时候并且选择跳过s的时候:

  • cache[ns][np] = any(cache[ns-1][np] + cache[ns-2][np] + ... cache[0][np])
  • cache[ns-1][np] = any(cache[ns-2][np] + ...cache[0][np])

因此: cache[ns][np] = any(cache[ns-1][np])即可

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        
        遇到*的时候，需要考虑 i到n位置的所有可能
        - *可以直接被跳过去，仅消耗p本身
        - *可以不被跳过去，消耗任意长度的s字符串，并进行遍历
        - 当p被消耗完的时候，s必须得被消耗完；当s被消耗完的时候，需要继续进行检查处理

        上一个版本的超时测试：太tmd长了
        "abbabbaaabababbaabaabbababbbbbbabaaababbabbaaabbbbbabbbbaaaaababbabaaabaaabaaabbbababbbabbabaaabaabaabbababaaabbbbaaababbabbabbabababaababbaaabbbbbbbabaaabbbabbbabaabbabaabbaaabbaabbaababaaabbbaabababaaab"
        "*ab**ba*a***ba******a*ba**ba**b***a*aabb*aaaa*a********a**b***abba**ab*ab*a**aba***b*a*b***bb****bba*aa"

        当遇到一个*号的时候并且选择跳过s的时候:
        cache[ns][np] = any(cache[ns-1][np] + cache[ns-2][np] + ... cache[0][np])
        cache[ns-1][np] = any(cache[ns-2][np] + ...cache[0][np])
        顾:
        cache[ns][np] = any(cache[ns-1][np])即可

        """
        cache = [["" for i in range(len(p) + 1)] for j in range(len(s)+1)]
        def match(s, p):
            # print(s, p)
            ns, np = len(s),len(p)
            if cache[ns][np] != "":
                return cache[ns][np]

            if len(p) == 0:
                return len(s) == 0
            
            rv = False
            # s可能只剩空字符了
            if p[0] == "*":
                choice_one = match(s, p[1:]) # 不消耗1个s，直接跳p
                # if s 为空，则不需要判断了
                # 通过公式推断，压缩了循环的变量
                choice_two = ns and match(s[1:], p)
                rv = choice_one or bool(choice_two)
            elif ns and p[0] in ("?", s[0]):
                rv = match(s[1:], p[1:])
            else:
                rv =  False
            cache[ns][np] = rv
            return rv
        return match(s, p)
  • 执行用时 :1276 ms, 在所有 Python 提交中击败了22.60%的用户
  • 内存消耗 :28.5 MB, 在所有 Python 提交中击败了25.00%的用户

Time Exceeded Version​

递归思路没问题，但是超时了。

  • 超时的输入
"abbabbaaabababbaabaabbababbbbbbabaaababbabbaaabbbbbabbbbaaaaababbabaaabaaabaaabbbababbbabbabaaabaabaabbababaaabbbbaaababbabbabbabababaababbaaabbbbbbbabaaabbbabbbabaabbabaabbaaabbaabbaababaaabbbaabababaaab"

"*ab**ba*a***ba******a*ba**ba**b***a*aabb*aaaa*a********a**b***abba**ab*ab*a**aba***b*a*b***bb****bba*aa"
time exceeded version
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        
        遇到*的时候，需要考虑 i到n位置的所有可能
        - *可以直接被跳过去，仅消耗p本身
        - *可以不被跳过去，消耗任意长度的s字符串，并进行遍历
        - 当p被消耗完的时候，s必须得被消耗完；当s被消耗完的时候，需要继续进行检查处理

          超时
          "aaabaaabaabababbabababaababbabbbbaaaaababbaabbbaab"
          "*babbbb*aab**b*bb*aa*"
        """

        def match(s, p):
            # print(s, p)
            if len(p) == 0:
                return len(s) == 0
            np, ns = len(p), len(s)
            # s可能只剩空字符了
            if p[0] == "*":
                rv = match(s, p[1:]) # 不消耗1个s，直接跳p
                flag = False
                # if s 为空，则不需要判断了
                if ns:
                    # 不消耗1个p，直接跳s,需要一直跳到s为空
                    # 否则如果是range(1, ns), 当ns==1的时候，该循环进不来
                    for i in range(1, ns+1):  
                        if match(s[i:], p):
                            flag = True
                            break
                return rv or flag
            elif ns and p[0] in ("?", s[0]):
                return match(s[1:], p[1:])
            return False
        return match(s, p)