#leetcode刷題之路44-通配符匹配

給定一個字元串 (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'。

思路1：

這是我第一反應的做法，就是用兩個指針按順序遍歷。因為遇到‘？’時和兩個字元相等是一樣的操作，所以這道題主要是討論遇到‘*’時的操作，這時需要加入一些輔助指針。

所有定義的指針為：ss（指向當前位置或pp遇到‘*’的位置）//// pp（指向一個普通位置或當前最後一個‘*’之後的位置） ////sstar (用於跳過s串中的字元)//// pstar（固定指向當前遇到的最後一個*）

#include <iostream>
using namespace std;

bool isMatch(string s, string p) {
    char*ss=(char*)s.data();
    char*pp=(char*)p.data();
    char*sstar= nullptr;
    char*pstar= nullptr;
    while(*ss)
    {
        if(*ss==*pp||*pp=='?')
        {
            ss++;
            pp++;
        }
        else if(*pp=='*')
        {
            pstar=pp++;
            sstar=ss;
        }
        else if(pstar)
        {
            pp=pstar+1;
            ss=++sstar;
        }
        else return false;
    }
    while(*pp == '*') ++pp;
    return !*pp;
}
int main() {
    string s="aaaa";
    string p="***a";
    std::cout <<isMatch(s,p) << std::endl;
    return 0;
}

思路二：

動態規劃法（https://www.cnblogs.com/daleyzou/p/9535134.html）：

bool isMatch(string s, string p) {
    bool **dp=new bool *[s.length()+1];//s.length()+1個bool*類型的一維指針
    for(int i=0;i<s.length()+1;i++)
    {
        dp[i]=new bool[p.length()+1];
        memset(dp[i],0,(p.length()+1)*sizeof(bool));
    }
    dp[0][0]= true;
    for(int i=0;i<p.length();i++)
    {
        if(dp[0][i]&&p[i]=='*')
            dp[0][i+1]=true;
    }

    for (int i = 0; i < s.length(); i++){
        for (int j = 0; j < p.length(); j++){
            if (p[j] == '*'){
                dp[i + 1][j + 1] = dp[i][j+1] || dp[i+1][j];
            }else if (p[j] == '?' || s[i] == p[j]){
                dp[i + 1][j + 1] = dp[i][j];
            }
        }
    }
    return dp[s.length()][p.length()];
}