题解 | #通配符匹配#

题目：通配符匹配

描述：请实现支持'?'and'*'.的通配符模式匹配

'?'可以匹配任何单个字符。
'*'可以匹配任何字符序列（包括空序列）。

返回两个字符串是否匹配

函数声明为：bool isMatch(const char *s, const char *p)

下面给出一些样例：

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "d*a*b") → false

示例1：输入："ab","?*"，返回值：true

解法一：

思路分析：通过题目分析我们可以大致了解题目的意思，主要是比较两个字符串是否相等，但是还包括两个通配字符，'?'表示可以匹配任何单个字符，'*'可以匹配任何字符序列（包括空序列），已知两个字符串指针：*s和*p，设定两个存储位置的指针变量char* spd主要用于存储S指针的位置和char* ppd用于存储p指针的位置，主要分为三种情况：

其一为，当s指针指向的字符与p指针指向的字符相等或者p指针为“？”代表两个字符匹配，直接进行下一轮的判断。比如"a", "?"，这两个字符串相等。

其二为，当p指针为“*”时，为这道题的重点，也就是可以匹配任何字符序列（包括空序列），这时候，我们就需要spd和ppd记录s和p指针的位置，然后通过设定的标记位进行循环判断。比如"aa", "*"返回true。

其三为，当两个字符串的值不相等时，可以直接返回false。比如"a","b"。

实例分析：输入："ab","?*"

第一次判断：因为s和p指针指向的内容分别为，a和？，所以可以进行下一次的判断。

第二次判断：当p为*时，就需要进行考虑了，因为不知道后面是否还存在字符，所以将s的字符位置赋给spd用于保存，将p指针的下一位赋给ppd，同样用于保存，（因为这一位*在这一次已经在进行考虑了），同时设置标记位为1。

第三次：最终输出true。

实例二："aab","a*b"

第一次判断：因为s和p指针指向的内容分别为，a和a，所以可以进行下一次的判断。

第二次判断：当p为*时，开始进行考虑，将s的字符位置ab赋给spd用于保存，将p指针的下一位b赋给ppd，同样用于保存，同时设置标记位为1。执行标记位程序，将s指向下一位，p指针指向ppd中的内容。

第三次判断：执行第一条程序判断值相同。

在程序的尾端我们应该注意的一点是，当s指针指向空时，p指针指向“*”的话，还是需要将p指针指向下一位，因为我们最后返回的值为!*p。

具体C程序为：

/**
 *
 * @param s string字符串
 * @param p string字符串
 * @return bool布尔型
 */
int isMatch(char* s, char* p ) {
    // write code here
    char* spd;//设置指针,主要用于存储S指针的字符
    char* ppd;//存储p指针的字符
    
    int specil = 0;//标记为
    while(*s){
        if(*s == *p || *p == '?'){//当两个指针指向相等或者是p指针所指字符位通配符?时
            s++;//判断下一位
            p++;//判断下一位
        }
        else if(*p == '*'){
            spd = s;//将s中的字符位置赋给spd
            ppd = ++p;//p走向下一位，记录当前位置的值
            specil = 1;//标记为设置位1
        }
        else if(specil){
            s = ++spd;//s可以与*匹配
            p = ppd;//返回p的位置值
        }
        else{
            return 0;
        }
    }
    while(*p == '*'){//监测空字符
        p++;
    }
    return !*p;
}

因为该程序循环的是s的全部字符，故时间复杂度为O(N)，N为s的长度，M为p的长度，当p的字符串长度大于s的字符串长度时，时间复杂度为O(M)，空间复杂度为O(N + M)。

解法二：

思路分析：我们通过上面分析可以得到一个基本的困惑就是，当发生通配符“*”匹配时应该是这道题最难的点，所以我们在第二种方法中从最简单的套路开始考虑，首先判断p的第一个元素是否为*，如果是的话，将问题转换为考虑该*匹配多少次的问题了，也就是判断isMatch(s[1:],p)和isMatch(s,p[1:])，如果p的第一个元素不是*的话，我们只要判断s[0]与p[0]能否匹配即可，我们用python进行编写。

Python代码为：

#
# 
# @param s string字符串 
# @param p string字符串 
# @return bool布尔型
#
class Solution:
    def isMatch(self , s , p ):
        # write code here
        s_len, p_len = len(s), len(p)#输出这两个字符串的长度
        mem = [[False]*(p_len + 1) for _ in range(s_len + 1)]##循环创建一个Plen+1为行和Slen+1为列的表格
        mem[0][0] = True#设置第一个元素为true
        for i in range(s_len + 1):#循环判断
            for j in range(1, p_len + 1):
                if p[j-1] == '*':#当为*的时候，考虑应该匹配多少次
                    mem[i][j] = mem[i][j-1]&nbs***bsp;(i > 0 and mem[i-1][j])
                else:#当不为#的时候考虑指针对应的值是否相等，以及另一个通配符“？”的情况
                    mem[i][j] = i > 0 and mem[i-1][j-1] and (s[i-1] == p[j-1]&nbs***bsp;p[j-1] == "?")
        return mem[-1][-1]

for循环存在循环Slen与Plen的情况，故其时间复杂度为O(N^2)，其中N为字符串s或者p的长度，设置了一个二维数组用于存放bool类型，故空间复杂度为O(N^2)。