陈中正的网络日志

LeetCode: Regular Expression Mathing

题目

https://oj.leetcode.com/problems/regular-expression-matching/

分析

  1. 普通字符和'.'的匹配很好解决, 直接匹配即可, 关键是'*'如何进行匹配

  2. 一开始我的想法是, ‘*’尽可能“贪婪”的匹配多个字符, 直到不再匹配为止。 然后在 s = "aaa", p = "a*a" 这个测试用例上跪了。。。

  3. 这说明'*'并不是尽可能多的进行匹配, 而是匹配一定数量的字符。 那么这个“一定数量”到底应该如何确定呢? 

可以这样确定, 每匹配一个字符, 就跳过'*'继续匹配下面的, 成功了就返回true, 如果失败了就返回'*'处再多匹配一个字符, 再跳过'*'匹配后面的……以此类推。 显然这的返回现场就是通过递归算法的DFS来实现了。

代码

class Solution
{
public:
    bool isMatch(const char *s, const char *p)
    {
        //递归基
        if (*p == '\0')
            return (*s == '\0');

        //如果下一个字符不是'*'
        if (*(p+1) != '*')
            return (*s != '\0') && (*s == *p || *p == '.') && isMatch(s+1, p+1);

        //如果下一个字符是'*'
        if (isMatch(s, p+2))
            return true;
        while ((*s != '\0') && (*s == *p || *p == '.')) 
        {
            s++;
            if (isMatch(s, p+2))
                return true;
        }
        return false;
    }
};

参考

http://leetcode.com/2011/09/regular-expression-matching.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39185791

Categories:  OJ题解 

« LeetCode: Maximum Subarray LeetCode: Reverse Integer »