【leetcode】 Wildcard Matching

地址

https://leetcode.com/problems/wildcard-matching/description/

题目

Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "cab") → false

思路

假设dpi表示p串前i位和s串前j位的匹配情况。则dpi有三种转移情况：

1. p[i+1]=='*' 则直接得到dpi+1=1
2. p[i+1]=='?' 则可以得到dpi+1=1,j<=k<s.size()
3. 如果p[i+1]==s[j+1]，则dpi+1=1。否则dpi+1=0;
   不过这题直接开个二维数组会爆内存（实际上有效状态并不多），所以需要改成递归的形式。改成递归形式后为了需要剪枝去除重复访问的状态，可用hash记录每个状态只访问一次。

代码

class Solution {
public:
    string a,b;
    int la,lb,ans=0;
    map<pair<int,int>,int>hs;
    
    void dfs(int x,int y)
    {
        if(hs[make_pair(x,y)])
            return;
        else
            hs[make_pair(x,y)]=1;
        if(x==la&&y==lb)
        {
            ans=1;return ;
        }
        else if(x==la||ans)
            return;
        else if(y==lb)
        {
            ans=1;
            for(int i=x;i<la&&ans;i++)
            if(a[i]!='*')
                ans=0;
            return;
        }
        if(a[x]=='?')
            dfs(x+1,y+1);
        else if(a[x]=='*')
            while(y<=lb)
                dfs(x+1,y++);
        else if(a[x]==b[y])
            dfs(x+1,y+1);
    }
    
    bool isMatch(string s, string p) {
        b=s,a=p;
        la=a.size(),lb=b.size();
        dfs(0,0);
        return ans==1;
    }
};