thumbnail: https://s2.ax1x.com/2019/04/05/ARfLq0.jpg
title: 44. Wildcard Matching
toc: true
tags: leetcode
categories: leetcode
comments: true

题目描述：通配符匹配

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

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

两个字符串完全匹配才算匹配成功
说明：

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

Input:
       s = "aa"
       p = "a"
Output:
       false
解释： "a"无法匹配"aa"整个字符串

示例2：

Input:
       s = "aa"
       p = "*"
Output:
       true
解释： "*"可以匹配任意字符串

示例3：

Input:
       s = "cb"
       p = "?a"
Output:
       false
解释： "?"可以匹配"c",但第二个"a"无法匹配"b"

示例4：

Input:
       s = "adceb"
       p = "a*b"
Output:
       true
解释： 第一个"*"可以匹配空字符串，第二个"*"可以匹配字符串"dce"

示例5：

Input:
       s = "acdcb"
       p = "a*c?b"
Output:
       false

分析：

• 通配符匹配的题目有一种利用动态规划的固定解法，即通过构造一个二维布尔值匹配数组，数组的最后一个元素即为返回结果
• 数组的构造得遵循一定规则

  以上表作为需要构造的数组arr，第一列表示模式串p的索引值，第一行表示匹配字符串s的索引值，索引值为0表示对应于空字符串。以下列情况对数组的构造进行解释：

• s=""和p="",arr[0][0]表示s为空和p为空的状态，此时p可以匹配s，因此arr[0][0]=true一定成立;

• p=""和s不为空时，s和p一定不匹配，因此，

• s=""和p不为空时，此时，只有p为一串*时,s和p才能够匹配，等价于p中当前字符为*，并且p的当前字符之前的子串与s能匹配;对应于表中如下，

  以上只是完成了数组的初始化，那数组中的元素该怎么复制呢？需要考虑一下集中情况：

• s="abc"和p="a*"能够匹配，可解读为："*"可以匹配"","a","ab","abc",因此能匹配即arr[i][j-1]=true&&p.charAt(i-1)==true，意为s中从0到当前字符构成的子串能否匹配，取决于s中从0到当前字符前一个字符构成的子串能否与p匹配;
• 讲解不清楚了，直接上代码吧。

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