LeetCode | Regular Expression Matching
发布日期:2021-09-08 22:55:13 浏览次数:6 分类:技术文章

本文共 2089 字,大约阅读时间需要 6 分钟。

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

思路是分别处理a*、.*、.、a的情况。

三周前写的lengthy code如下:

1 class Solution { 2 public: 3
 bool isMatch(const char *s, const char *p) { 4
 int sn = strlen(s); 5
 int pn = strlen(p); 6
 return recursive(s, sn, p, pn); 7
 } 8
  9
 bool recursive(const char* s, int sn, const char* p, int pn) {10
 if (sn == 0 && pn == 0) return true;11
 if (pn == 0) return false;12
 13
 if (*(p + 1) != '\0') {14
 if (*(p + 1) == '*') {15
 if (*p == '.') { // .*16
 int n = 0;17
 while (n <= sn) {18
 if (recursive(s + n, sn - n, p + 2, pn - 2)) return true;19
 n++;20
 }21
 } else { // a*22
 int n = 0;23
 while (n <= sn && *(s + n) == *p) {24
 if (recursive(s + n, sn - n, p + 2, pn - 2)) return true;25
 n++;26
 }27
 if (recursive(s + n, sn - n, p + 2, pn - 2)) return true;28
 }29
 } else {30
 if (*p != '.' && *s != *p) return false;31
 if (recursive(s + 1, sn - 1, p + 1, pn - 1)) return true;32
 }33
 } else {34
 if (*p != '.' && *s != *p) return false;35
 if (recursive(s + 1, sn - 1, p + 1, pn - 1)) return true;36
 }37
 }38 };

今天看了Leetcode上1337的代码真是羞愧啊。

重写了一遍。思路还是一样。

1 class Solution { 2 public: 3
 bool isMatch(const char *s, const char *p) { 4
 if (*p == '\0') return (*s == '\0'); 5
 // match single '\0', '.', 'a'... 6
 if (*(p + 1) != '*') {  7
 return ((*s == *p || (*p == '.' && *s != '\0')) && isMatch(s + 1, p + 1)); 8
 } 9
 10
 // match a*, .*11
 while ((*s == *p || (*p == '.' && *s != '\0'))) {12
 if (isMatch(s++, p + 2)) return true;13
 }14
 15
 // ignore a*, *p != '.' && *s != *p16
 return isMatch(s, p + 2);17
 }18 };

 

转载于:https://www.cnblogs.com/linyx/p/3713825.html

转载地址:https://blog.csdn.net/weixin_34341229/article/details/93407195 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Javascript 篱式条件判断
下一篇:python实现生产者消费者模型

发表评论

最新留言

感谢大佬
[***.191.171.5]2022年08月16日 15时38分06秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章