【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", "ca*b") → false

思路

假设dp[i][j]表示p串前i位和s串前j位的匹配情况。则dp[i][j]有三种转移情况: 1. p[i+1]=='*' 则直接得到dp[i+1][j+1]=1 2. p[i+1]=='?' 则可以得到dp[i+1][k]=1,j<=k<s.size() 3. 如果p[i+1]==s[j+1],则dp[i+1][j+1]=1。否则dp[i+1][j+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;
    }
};