找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6891|回复: 19
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Regular Expression Matching】-【刷题第一弹2014】

[复制链接]

91

主题

47

精华

1916

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1916

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 11-27-2014 02:20 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-4-2014 11:59 AM 编辑

快速通道:
https://oj.leetcode.com/problems/regular-expression-matching/

Implement regular expression matching with support for '.' and '*'.

建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                        汇总贴 传送门
==================================

本帖被以下淘专辑推荐:

发表于 11-27-2014 01:37 PM | 显示全部楼层
本帖最后由 cpcs 于 12-4-2014 12:34 AM 编辑

思路:
递归,可以记录状态 比如一个前i位 和一个前j位 类似dp,当然也可以记录第一个前i位,最长match到第二个前多少位……不过这些虽然能优化时间复杂度,但不好讲 。。。所以不建议写。
代码:
  1. class Solution {
  2. public:
  3.     bool isMatch(const char *s, const char *p) {
  4.         if (*p == 0) {
  5.             return *s == 0;
  6.         }
  7.         if (*(p + 1) == '*') {
  8.             for (;;++s) {
  9.                 if (isMatch(s, p + 2)) {
  10.                     return true;
  11.                 }
  12.                 if ((*s == 0) || ((*s != *p) && (*p != '.'))) {
  13.                     break;
  14.                 }
  15.             }
  16.             return false;
  17.             
  18.         }
  19.         else if (*s == 0) {
  20.             return false;
  21.         }
  22.         else {
  23.             return ((*p == '.') || (*s == *p)) && isMatch(s + 1, p + 1);
  24.         }
  25.         
  26.     }
  27. };
复制代码


复杂度分析:不优化是指数,优化可以到len1 * len2
细节和陷阱:注意代码清晰度,不光要写对,还要讲清楚,所以不建议优化。


我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

18

主题

9

精华

522

积分

超级会员

Rank: 4

积分
522
发表于 11-27-2014 07:38 PM | 显示全部楼层
感觉这道题用迭代可能更清楚一点,重要的一点就是是否有*号的出现,复杂度可以达到O(len1 + len2)
  1. class Solution {
  2. public:
  3.     bool isMatch(const char *s, const char *p) {
  4.         if(*p == '\0') return *s == '\0';
  5.         
  6.         if(*(p+1) != '*'){
  7.             if(*s == *p || ( *p == '.' && *s != '\0' ))
  8.                 isMatch(s+1, p+1);
  9.             else
  10.                 return false;
  11.         }else{
  12.             while(*s == *p || (*p == '.' && *s != '\0')){
  13.                 if(isMatch(s, p + 2))
  14.                     return true;
  15.                 s++;
  16.             }
  17.             return isMatch(s, p+2);
  18.         }
  19.     }
  20. };
复制代码

补充内容 (11-27-2014 07:40 PM):
说错了,应该是递归会更容易理解一点
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表