算法设计与分析（7）-- Regular Expression Matching（难度：hard）

算法设计与分析（7）

题目：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

算法思路：

这条题目是求一个字符串s是否满足一个正则表达式p。这里我们可以使用最基本的动态规划。一开始，我们先讨论最基本的情况。 1.首先，如果两个字符串s，p都是空字符串，直接返回true：

if (s.empty() && p.empty()) return true;

2.否侧，如果p为空字符串，返回false：

else if ( p.empty()) return false;

3.否则，如果s为空字符串 并且 p[1] =="*"这个时候我们是不能直接得到结果的，例如：s="", p="a*a*" 结果为true，s="", p="a*a" 结果为false。所以我们使用递归：

else if (s.empty() && p[1] == '*') return isMatch(s, p.substr(2));

4.否则，如果s为空字符串，直接返回false：

else if (s.empty()) return false;

5.否则，当s和p都不是空字符串的时候，我们开始详细分情况讨论： （1）如果p[1] == '*'成立，当下面条件：(a)isMatch(s, p.substr(2)) (b) (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p)，只要(a) 或 (b) 其中一个为true就好； （2）如果s[0] == p[0] || p[0] == '.' 成立，我们可以直接匹配他们的子串； （3）别的情况可以直接返回false。

else { if (p[1] == '*') return (isMatch(s, p.substr(2)) || ((s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p))); else if (s[0] == p[0] || p[0] == '.') return isMatch(s.substr(1), p.substr(1)); else return false; }

实现代码：

#include<iostream> #include<string> using namespace std; bool isMatch(string s, string p) { if (s.empty() && p.empty()) return true; else if ( p.empty()) return false; else if (s.empty() && p[1] == '*') return isMatch(s, p.substr(2)); else if (s.empty()) return false; else { if (p[1] == '*') return (isMatch(s, p.substr(2)) || ((s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p))); else if (s[0] == p[0] || p[0] == '.') return isMatch(s.substr(1), p.substr(1)); else return false; } } int main() { string s = "a"; string p = ".*..a*"; bool t = isMatch(s, p); cout << t << endl; return 0; }