LeetCode刷题（C++）——Regular Expression Matching（Hard）

叁歲伎倆 2022-06-16 02:09 140阅读 0赞

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

class Solution {
    public:
        bool isMatch(string s, string p) {
            if (p.empty())
    			return s.empty();
    		if (p.size() == 1)
    			return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
    		if (p[1] != '*')
    		{
    			if (s.empty())
    				return false;
    			else
    				return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
    		}
    		while (!s.empty() && (s[0] == p[0] || p[0] == '.'))
    		{
    			if (isMatch(s, p.substr(2)))
    				return true;
    			s = s.substr(1);
    		}
    		return isMatch(s, p.substr(2));
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 刷题

* [Leetcode 9. 回文数][Leetcode 9.] * [Leetcode 125. 验证回文串][Leetcode 125.] * [Leetc...

た入场券/ 2024年04月18日 12:09/ 0 赞/ 110 阅读

相关 leetcode刷题纪要

2020-01-11 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

ゞ浴缸里的玫瑰/ 2023年01月05日 01:26/ 0 赞/ 142 阅读

相关 LeetCode刷题目录

<table> <tbody> <tr> <th colspan="3">LeetCode刷题目录</th> </tr> <tr> <th

待我称王封你为后i/ 2022年12月29日 04:53/ 0 赞/ 177 阅读

相关 LeetCode刷题笔记

文章目录 1.数据结构 1.1字符串、数组、链表 1.2队列、栈 1.3堆 1.4树 1.

向右看齐/ 2022年11月19日 07:54/ 0 赞/ 266 阅读

相关 leetcode刷题记录

\\ leetcode刷题记录 \\ 别人的刷题记录：[leetcode题解一览表][leetcode] 1052. 爱生气的书店老板看到了位置可选的长度

野性酷女/ 2022年10月31日 15:53/ 0 赞/ 219 阅读

相关 LeetCode刷题（C++）——Regular Expression Matching（Hard）

Implement regular expression matching with support for `'.'` and `''`. '.' Matches

叁歲伎倆/ 2022年06月16日 02:09/ 0 赞/ 141 阅读

相关 [leetcode]: 刷题目录

题目分类，博客对应连接，方便查找 1.树路径和 [112. Path Sum][] [437. Path Sum III][] 遍历 [104. Maxi

女爷i/ 2022年06月15日 11:17/ 0 赞/ 257 阅读

相关 LeetCode刷题答案

目录 3. 无重复字符的最长子串 4. 寻找两个有序数组的中位数 5. 最长的回文子串 6.Z 字形变换 8. 字符串转换整数 (atoi) 9. 回文数

比眉伴天荒/ 2022年04月24日 09:46/ 0 赞/ 316 阅读

相关 LeetCode刷题指南

以下是我个人做题过程中的一些体会： 1. LeetCode的题库越来越大，截止到目前，已经有321个问题了。对于大多数人来说，没有时间也没有必要把所有题目都做一遍（时间充

àì夳堔傛蜴生んèń/ 2022年02月04日 20:30/ 0 赞/ 339 阅读

相关 Leetcode刷题

39. 组合总和给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

秒速五厘米/ 2021年06月10日 20:37/ 0 赞/ 594 阅读