首页 > 代码库 > [LeetCode]wildcard matching通配符实现之贪心法

[LeetCode]wildcard matching通配符实现之贪心法

2024-07-18 07:21:01   221人阅读

前天用递归LTE,昨天用动态规划LTE,今天接着搞，改用贪心法。题目再放一次：

‘?‘匹配任意字符，‘*‘匹配任意长度字符串

Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "c*a*b") → false
The function prototype should be:bool isMatch(const char *s, const char *p)
思路其实更简单,和递归的有点像,两个字符串从头开始匹配，不匹配直接返回false，匹配，则两个指针都加1,若p遇到*,则s++一直到匹配到p+1,当然要记录此时p和s的位置,以便下次回溯.
还是用图片说明吧:


用该方法,最差情况下复杂度为len_s*len_p,绝大情况下其实小很多.具体代码如下:
class Solution {public:    bool isMatch(const char *s, const char *p) {        const char *last_s = NULL;        const char *last_p = NULL;        while (‘\0‘ != *s || ‘*‘ == *p)        {            if (*s == *p || ‘?‘ == *p)            {                s++;                p++;                continue;            }            if (‘*‘ == *p)            {                while (‘*‘ == *p)                {                    last_p = p;                    p++;                }                while (‘\0‘ != *s && (*s != *p && ‘?‘ != *p))                {                    s++;                }                last_s = s;                continue;            }            if (last_p != NULL)            {                p = last_p;                s = last_s+1;                continue;            }            return false;        }        if (‘\0‘ == *p)        {            return true;        }        return false;    }};
这次终于AC了.
最初的时候直观的感觉如果p中有n个*就要保存多个n个位置以回溯,其实不用,只要保证前面的子串匹配了,后面的*匹配不受影响,就是有多种匹配方案,但是只要找到一种就可以了.
这个解决方案感觉不是很美,一是思路不清爽,很容易忽略一些特殊情况,Wrong Answer了两次才成功;二是不像前两种,能解决s和p都带有通配符的情况,只能做只有p中有通配符,s中也有的情况感觉分析起来很复杂,不直观.
































        

            
                
                  
                
                

                    联系

                    我们