通配符匹配

携手创作，一起成长！这是我参与「日新计划 8 月更文应战」的第2天，点击查看活动详情

一、题目

LeetCode 通配符匹配

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

二、题解

给定有两个字符串，看两个字符串是否彻底匹配得上。能够说字符串s便是匹配字符串，字符串p便是待匹配字符串，要用字符串p去匹配字符串s，字符串p中或许存在的?和*字符能够相应的抵消字符串s的某些字符来使得两个字符串能够匹配（纷歧定是要两个字符串的字符彻底持平）。

办法一
依据题意，字符串s中只会存在小写字母或者为空，而字符串p同样或许为空或者只存在小写字母以及匹配字符?和*。而?字符能够匹配恣意一个字符，*字符能够匹配空字符串或者恣意的字符串，也便是能够匹配多个接连的字符。对此能够使用动态规划来枚举匹配，定义一个dp数组，用dp[i][j]表明字符串s的前i个字符与字符串p的前j个字符是否匹配。初始的对于两个字符串都是空的时也能匹配得了即dp[0][0] = true。然后遍历两个字符串的字符来枚举匹配，对于字符串p的字符如果是小写字母的话，那么字符串s中也得是对应的字母才干匹配的上；如果是?字符的话字符串s能够的恣意的字母即dp[i][j] = dp[i - 1][j - 1]；如果是*字符的话字符串s也能够是恣意的字符或者是多个字符即dp[i][j] = dp[i][j - 1] || dp[i - 1][j]。当遍历完毕的时候返回最后计算的结果即可。

三、代码

办法一
Java代码

class Solution {
    public boolean isMatch(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];
        dp[0][0] = true;
        for (int i = 1; i <= pLen; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= sLen; ++i) {
            for (int j = 1; j <= pLen; ++j) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[sLen][pLen];
    }
}

时刻复杂度：O(n^2)，需求遍历两个字符串的字符。

空间复杂度：O(n^2)，动态规划需求一个dp数组。