欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

正则表达式匹配(递归)

程序员文章站 2024-02-20 14:17:52
...

正则表达式匹配(递归)
正则表达式匹配(递归)

class Solution {
public:
	bool isMatch(string s, string p) {
		//如果正则串p为空且字符串s也为空则匹配成功,如果正则串p为空但是s不为空则说明匹配失败
		if (p.empty())return s.empty();
		//判断s和p的首字符是否匹配,注意要先判断s不为空(因为能执行下面这句话本身就说明p不为空了)
		bool headMatched = !s.empty() && (s[0] == p[0] || p[0] == '.');
		if (p.length() >= 2 && p[1] == '*')
		{
			//如果p的第一个元素的下一个元素是*,则分别对两种情况进行判断
			return isMatch(s, p.substr(2)) || (headMatched&&isMatch(s.substr(1), p));
		}
		else if (headMatched)
		{
			//否则,如果s和p的首字符相等,则s和p同时后移一位继续判断
			return isMatch(s.substr(1), p.substr(1));
		}
		else
			return false;
	}
};
相关标签: 回溯