Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Wildcard Matching

Leetcode algorithms 第 44 题:Wildcard Matching 。

题目

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", "c*a*b") → false

解答

直接使用递归会超出内存或者超时,因为递归会重复计算很多相同的内容,可以使用动态规划利用中间结果来避免重复计算。

用dp[i][j]表示s串的前i个字符和p串的前j个字符是否匹配,则计算p[i][j]时,可以根据p的第j个字符分别讨论

  • p[j-1]为*,此时s可以选择使用这个*,问题转化为dp[i-1][j];或者不使用这个*,变为dp[i][j-1]。
  • p[j-1]为?,此时p[j-1]必定要匹配s[i-1]。
  • p[j-1]为普通字符,如果p[j-1]==s[i-1],匹配成功,问题转化为dp[i-1][j-1],否则匹配失败,dp[i][j] = false。

当i或j为0时作为初始化部分,根据定义,应有:

  • dp[0][0] = true。
  • dp[i][0] = false,因为有长度的s肯定无法和空串p匹配。
  • dp[0][i],只有p[i-1]为*且dp[0][i-1]为真是才为真。

根据以上思想可以容易写出代码如下:

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int ls = strlen(s), lp = strlen(p);
        
        int cnt = 0; //统计p匹配字符的最小长度
        for (const char *i = p; *i; i++)
            if (*i != '*') cnt++;
        if (cnt > ls) return false;
        
        //dp[i][j]:s的前i个字符能否匹配p的前j个字符
        vector<vector<bool>> dp(ls + 1, vector<bool>(lp + 1, false));
        
        //初始化,dp[0][0]为真,dp[i][0]始终为假,dp[0][i]需要p一直为*才为真
        dp[0][0] = true;
        for (int i = 1; i <= lp; i++)
            dp[0][i] = p[i-1] == '*' && dp[0][i-1];

        for (int i = 1; i <= ls; i++)
            for (int j = 1; j <= lp; j++)
            {
                if (p[j-1] == '*') //*号可以匹配,也可以不匹配
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                else if (p[j-1] == '?' || s[i-1] == p[j-1]) //?号或者相等
                    dp[i][j] = dp[i-1][j-1];
            }
        return dp[ls][lp];
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论