LeetCode Wildcard Matching DP/贪心

时间:2022-09-01 20:47:22

这道题按理来说应该是Regular Expression Matching的简单版,但是测试数据较多较复杂,用普通的dfs会超时,常规dp会超内存,因此需要进行额外的处理。

方法一:DP

常规DP使用二维数组LeetCode Wildcard Matching DP/贪心表示s中前i个字符和p中前j个字符的匹配情况,但其实存在冗余,具体可以观察动态转移方程:

LeetCode Wildcard Matching DP/贪心

其实当前状态至多与前一轮的状态相关,将i作为外层循环的话,要求解LeetCode Wildcard Matching DP/贪心,只需LeetCode Wildcard Matching DP/贪心,令LeetCode Wildcard Matching DP/贪心表示前一轮(s的前一个位置与p[j+1]的匹配关系),则动态转移方程可以改为:

LeetCode Wildcard Matching DP/贪心

简单来看,就是用pre[]替换dp[i][],因为pre代表的是前一轮的匹配状态。然后每一轮循环进行完之后要更新pre。

代码如下,Runtime: 444 ms:

class Solution {
public:
    bool isMatch(string s, string p) {
        int len1 = s.size(), len2 = p.size();
        bool dp[len2 + 1], pre[len2 + 1];
        memset(dp, false, sizeof(dp));
        memset(pre, false, sizeof(pre));
        pre[0] = true;
        for(int i = 0; i < len2; ++i)
            pre[i + 1] = p[i] == '*' ? pre[i] : false;
        if(len1 == 0)
            return pre[len2];
        for(int i = 0; i < len1; ++i){
            for(int j = 0; j < len2; ++j){
                if(p[j] == '*')
                    dp[j + 1] = pre[j + 1] || dp[j];
                else
                    dp[j + 1] = (p[j] == '?' || p[j] == s[i]) ? pre[j] : false;
            }
            for(int j = 0; j <= len2; ++j)
                pre[j] = dp[j];
        }
        return dp[len2];
    }
};

方法二:贪心

使用递归TLE的主要原因是分支太多,回溯耗时。引起回溯的是‘*’号的匹配,常规dfs中,对每一个‘*’号都进行了扩展(依次匹配0个,1个……),当失配时再回溯到该‘*’号。所以减少回溯的切入点就是减少需要回溯的‘*’号。贪心的思路是:只对最后一个‘*’号进行回溯。每当失配时,只回溯到最近的一个‘*’号,令该‘*’号多匹配一个字符,重新进行匹配。

证明如下:令LeetCode Wildcard Matching DP/贪心为最近的‘*’号,与之对应的是LeetCode Wildcard Matching DP/贪心(显然LeetCode Wildcard Matching DP/贪心已经匹配)。若当前对star的扩展嵌套在前一个‘*’号LeetCode Wildcard Matching DP/贪心的扩展中,设LeetCode Wildcard Matching DP/贪心匹配了x个字符,处理到LeetCode Wildcard Matching DP/贪心时失配,需要回溯。则最优解为回溯到star,从LeetCode Wildcard Matching DP/贪心开始重新匹配。假设存在另一个最优解是回溯到LeetCode Wildcard Matching DP/贪心,由于失配,所以LeetCode Wildcard Matching DP/贪心应该尝试匹配x + 1个字符。假设我们足够幸运,使得LeetCode Wildcard Matching DP/贪心匹配(*号多匹配一个字符),则此时与LeetCode Wildcard Matching DP/贪心对应的是LeetCode Wildcard Matching DP/贪心。二者得到的结果相同,但后者多付出了一次回溯。因此最优解为:回溯到最近的(last)一个‘*’号。

具体处理方法是:维护两对指针,一对指明s,p开始匹配的位置(该位置处p为'*'号)sbeg/star,一对表示当前匹配的位置s_cur/p_cur。

①若*p_cur == '?' || *p_cur == *s_cur,则当前位置匹配,两个指针都继续右移,++s_cur, ++p_cur

②若*p_cur == '*',则该‘*’号可以匹配任意个字符,首先从0开始尝试,star = p_cur,sbeg = s_cur,++p_cur(待匹配位置)

③否则失配,需要回溯到上一个'*'号,s_cur = ++sbeg, p_cur = star + 1

代码如下,Runtime: 20 ms

class Solution {
public:
    bool isMatch(string s, string p) {
        const char* star = NULL;
        const char *s_beg = s.c_str(), *s_cur = s_beg, *p_cur = p.c_str();
        while(*s_cur){
            if(*p_cur == '?' || *p_cur == *s_cur)
                ++s_cur, ++p_cur;
            else if(*p_cur == '*')
                star = p_cur, s_beg = s_cur, ++p_cur;
            else if(star)
                s_cur = ++s_beg, p_cur = star + 1;
            else
                return false;
        }
        while(*p_cur == '*')
            ++p_cur;
        return *p_cur == '\0';
    }
};