首页 > 代码库 > Regular Expression Matching

Regular Expression Matching

10. Regular Expression Matching

题目链接:https://leetcode.com/problems/regular-expression-matching/#/description

题目大意:实现一个正则表达式匹配函数。该正则表达式支持‘.‘和‘*‘。其中‘.‘匹配任意的单个字符,‘*‘匹配0个或多个前一个字符。函数参数为两个字符串s和p,如果s可以被p完全匹配,则返回true,否则返回false。

 

思路:可以对多种情况进行分类讨论。1、如果p为空字符串,则直接判断s是否为空即可;2、p不为空,且p只包含一个字符,完全匹配的条件为s与p相等或者s只包含一个字符,且p[0]==‘.‘;3、p.size()>=2且p[1]==‘*‘,因为‘*‘匹配0个或多个前一个字符,所以s与p是否匹配可以转换为:(1)s与p.substr(2)是否匹配,这时‘*‘匹配0个前一个字符;(2)s.substr(1)与p是否匹配,这时‘*‘匹配多个前一个字符(前提条件是s[0]与p[0]匹配);4、p.size()>=2且p[1]!=‘*‘,完全匹配的条件为s不为空,s[0]与p[0]匹配且s.substr(1)与p.substr(1)匹配。

算法复杂度:时间复杂度为O(n),空间复杂度为O(n)。

代码:

 1 class Solution {
 2 public:
 3     bool isMatch(string s, string p) {
 4         if (p.empty())
 5             return s.empty();
 6         if (p.size() >= 2 && p[1] == *)
 7             return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == .) && isMatch(s.substr(1), p));
 8         else
 9             return !s.empty() && (s[0] == p[0] || p[0] == .) && isMatch(s.substr(1), p.substr(1));
10     }
11 };

评测系统上运行结果:

技术分享

 

Regular Expression Matching