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

Leetcode Regular Expression Matching

Leetcode algorithms 第 10 题:Regular Expression Matching。

题目

Implement regular expression matching with support for ‘.’ and ‘*’.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

解答

注意,这里的*不是匹配0个或多个任意字符,其是匹配前一个字符出现0次或任意次。这里使用递归进行解决。

首先考虑字符匹配的情况,s和p相等时必然匹配,s的任意字符和p的字符.也匹配,注意,.和*可以同时使用,意味着.*可以匹配任意字符串。

  • 当p的下一个字符为*时,这两个字符需要连续使用,考虑*匹配s中的一个或多个时,递归进行判断,直到和*搭配的字符在s中不再出现位置。
  • 当p的下一个字符不为*时,可以简单地匹配,然后递归。

具体代码如下:

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (!s || !p) return false; //任一个为NULL返回false
        
        if (!*p) return *s == '\0'; //两个为空时返回true
        
        if (*(p+1) == '*') //后一个为*,需要组合使用
        {
            while (true) //*可以匹配0个或多个
            {
                if (isMatch(s, p+2)) return true;
                if (*s == *p || (*p == '.' && *s != '\0')) s++;
                else break;
            }
        }
        else if(*s == *p || (*p == '.' && *s != '\0'))
            return isMatch(s+1, p+1);
        
        return false;
    }
};
上一篇: 下一篇:

我的博客

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

站内搜索

最新评论