二哥的 LeetCode 刷题笔记：044 通配符匹配

作者：沉默王二
发布时间：2022-09-27T09:54:27.184+0800

---

044.通配符匹配

题意

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

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

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

说明:

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

难度

困难

示例

示例 1:

输入:

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

示例 2:

输入:

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

示例 3：

输入:

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

分析

在 010.正则式匹配 这道题中，我们使用了 “动态规划” 的方案来解题。

那现在遇到了相似的题目，能不能继续采用动态规划的方式来解决呢？

完全可以！

先来约定一些规则方便下文的讲解：

给定的模式 p 中，只会有三种类型的字符出现：

• 小写字母 a-z，可以匹配对应的一个小写字母；
• 问号 ?，可以匹配任意一个小写字母；
• 星号 *，可以匹配任意字符串，可以为空，也就是匹配零或任意多个小写字母。

然后：

• 字符串 s 的开始位置为1
• 空串表示字符串的位置为0
• f[i][j]（f 为一个 boolean 的二维数组，一维的长度为s.length() + 1，s 为字符串，二维的长度为p.length() + 1，p 为字符模式）表示s串的1-i的子串能够成功匹配上p的1-j的子串

首先，空串肯定是可以与空串匹配的，所以f[0][0] = true表示s的空串和p的空串能够匹配成功，这就是我们 动态规划 的开始。

如果没有*的时候，应该怎么处理呢？

那显然可以直接挨个匹配过去，两个字符相同或者是p.charAt(j)为?且之前匹配成功，就算匹配成功，即

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {

}

OK。

接下来还有一个最令人头疼的问题——*，因为它能匹配0个或者任意多个，所以究竟要让它怎么去匹配，是这题最困难的地方，但不用急，毕竟只剩下它没有解决了（😂）。

想一下。

我们利用f[i][j]表示s串的1-i的子串能够成功匹配上p的1-j的子串。

那么如果p.charAt(j) == '*'且我们不拿来匹配的话，实际上是把这个位置给跳过了，那么f[i][j]其实就和f[i][j - 1]的取值一样，因为j - 1使用的是p.charAt(j)之前的状态。

而我们如果拿来配了呢？

因为可以匹配任意多个，所以f[i][j]的取值就和f[i - 1][j]的取值一样，等i增加的时候如果再次遇到了当前这个位置的，它也能够再次匹配。

最后注意一下实际中字符串的存储是从0位置开始的，就可以解决这道题目了。

class Solution {

        boolean[][] f = new boolean[s.length() + 1][p.length() + 1];        f[0][0] = true;        for(int i = 1;i <= p.length();i++){            if(p.charAt(i-1) == '')                f[0][i] = true;            else                break;        }        for(int i = 1;i <= s.length();i++)            for(int j = 1;j <= p.length();j++){                if(p.charAt(j - 1) == '')                    f[i][j] = f[i][j - 1] | f[i - 1][j];                else                    if(p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?')                        f[i][j] = f[i - 1][j - 1];            }        return f[s.length()][p.length()];    }}

总结

本次我们再次利用了 动态规划 的方法来解决字符串问题，实际上这个问题被我们剖析为三种情况，一种是普通的字符串完全匹配，一种是带有问号的，最后一种则是带有的，前面两个问题都解决了之后，我们再来面对这个大Boss，这样就比直接硬抗整个大问题变得更加容易去解决。

力扣链接：https://leetcode.cn/problems/wildcard-matching/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 850 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

044.通配符匹配

题意

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

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

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

说明:

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

难度

困难

示例

示例 1:

输入:

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

示例 2:

输入:

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

示例 3：

输入:

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

分析

在 010.正则式匹配 这道题中，我们使用了 “动态规划” 的方案来解题。

那现在遇到了相似的题目，能不能继续采用动态规划的方式来解决呢？

完全可以！

先来约定一些规则方便下文的讲解：

给定的模式 p 中，只会有三种类型的字符出现：

• 小写字母 a-z，可以匹配对应的一个小写字母；
• 问号 ?，可以匹配任意一个小写字母；
• 星号 *，可以匹配任意字符串，可以为空，也就是匹配零或任意多个小写字母。

然后：

• 字符串 s 的开始位置为1
• 空串表示字符串的位置为0
• f[i][j]（f 为一个 boolean 的二维数组，一维的长度为s.length() + 1，s 为字符串，二维的长度为p.length() + 1，p 为字符模式）表示s串的1-i的子串能够成功匹配上p的1-j的子串

首先，空串肯定是可以与空串匹配的，所以f[0][0] = true表示s的空串和p的空串能够匹配成功，这就是我们 动态规划 的开始。

如果没有*的时候，应该怎么处理呢？

那显然可以直接挨个匹配过去，两个字符相同或者是p.charAt(j)为?且之前匹配成功，就算匹配成功，即

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {

}

OK。

接下来还有一个最令人头疼的问题——*，因为它能匹配0个或者任意多个，所以究竟要让它怎么去匹配，是这题最困难的地方，但不用急，毕竟只剩下它没有解决了（😂）。

想一下。

我们利用f[i][j]表示s串的1-i的子串能够成功匹配上p的1-j的子串。

那么如果p.charAt(j) == '*'且我们不拿来匹配的话，实际上是把这个位置给跳过了，那么f[i][j]其实就和f[i][j - 1]的取值一样，因为j - 1使用的是p.charAt(j)之前的状态。

而我们如果拿来配了呢？

因为可以匹配任意多个，所以f[i][j]的取值就和f[i - 1][j]的取值一样，等i增加的时候如果再次遇到了当前这个位置的，它也能够再次匹配。

最后注意一下实际中字符串的存储是从0位置开始的，就可以解决这道题目了。

class Solution {

        boolean[][] f = new boolean[s.length() + 1][p.length() + 1];        f[0][0] = true;        for(int i = 1;i <= p.length();i++){            if(p.charAt(i-1) == '')                f[0][i] = true;            else                break;        }        for(int i = 1;i <= s.length();i++)            for(int j = 1;j <= p.length();j++){                if(p.charAt(j - 1) == '')                    f[i][j] = f[i][j - 1] | f[i - 1][j];                else                    if(p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?')                        f[i][j] = f[i - 1][j - 1];            }        return f[s.length()][p.length()];    }}

总结

本次我们再次利用了 动态规划 的方法来解决字符串问题，实际上这个问题被我们剖析为三种情况，一种是普通的字符串完全匹配，一种是带有问号的，最后一种则是带有的，前面两个问题都解决了之后，我们再来面对这个大Boss，这样就比直接硬抗整个大问题变得更加容易去解决。

力扣链接：https://leetcode.cn/problems/wildcard-matching/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 850 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

044.通配符匹配

题意

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

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

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

说明:

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

难度

困难

示例

示例 1:

输入:

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

示例 2:

输入:

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

示例 3：

输入:

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

分析

在 010.正则式匹配 这道题中，我们使用了 “动态规划” 的方案来解题。

那现在遇到了相似的题目，能不能继续采用动态规划的方式来解决呢？

完全可以！

先来约定一些规则方便下文的讲解：

给定的模式 p 中，只会有三种类型的字符出现：

• 小写字母 a-z，可以匹配对应的一个小写字母；
• 问号 ?，可以匹配任意一个小写字母；
• 星号 *，可以匹配任意字符串，可以为空，也就是匹配零或任意多个小写字母。

然后：

• 字符串 s 的开始位置为1
• 空串表示字符串的位置为0
• f[i][j]（f 为一个 boolean 的二维数组，一维的长度为s.length() + 1，s 为字符串，二维的长度为p.length() + 1，p 为字符模式）表示s串的1-i的子串能够成功匹配上p的1-j的子串

首先，空串肯定是可以与空串匹配的，所以f[0][0] = true表示s的空串和p的空串能够匹配成功，这就是我们 动态规划 的开始。

如果没有*的时候，应该怎么处理呢？

那显然可以直接挨个匹配过去，两个字符相同或者是p.charAt(j)为?且之前匹配成功，就算匹配成功，即

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {

}

OK。

接下来还有一个最令人头疼的问题——*，因为它能匹配0个或者任意多个，所以究竟要让它怎么去匹配，是这题最困难的地方，但不用急，毕竟只剩下它没有解决了（😂）。

想一下。

我们利用f[i][j]表示s串的1-i的子串能够成功匹配上p的1-j的子串。

那么如果p.charAt(j) == '*'且我们不拿来匹配的话，实际上是把这个位置给跳过了，那么f[i][j]其实就和f[i][j - 1]的取值一样，因为j - 1使用的是p.charAt(j)之前的状态。

而我们如果拿来配了呢？

因为可以匹配任意多个，所以f[i][j]的取值就和f[i - 1][j]的取值一样，等i增加的时候如果再次遇到了当前这个位置的，它也能够再次匹配。

最后注意一下实际中字符串的存储是从0位置开始的，就可以解决这道题目了。

class Solution {

        boolean[][] f = new boolean[s.length() + 1][p.length() + 1];        f[0][0] = true;        for(int i = 1;i <= p.length();i++){            if(p.charAt(i-1) == '')                f[0][i] = true;            else                break;        }        for(int i = 1;i <= s.length();i++)            for(int j = 1;j <= p.length();j++){                if(p.charAt(j - 1) == '')                    f[i][j] = f[i][j - 1] | f[i - 1][j];                else                    if(p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?')                        f[i][j] = f[i - 1][j - 1];            }        return f[s.length()][p.length()];    }}

总结

本次我们再次利用了 动态规划 的方法来解决字符串问题，实际上这个问题被我们剖析为三种情况，一种是普通的字符串完全匹配，一种是带有问号的，最后一种则是带有的，前面两个问题都解决了之后，我们再来面对这个大Boss，这样就比直接硬抗整个大问题变得更加容易去解决。

力扣链接：https://leetcode.cn/problems/wildcard-matching/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 850 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412