一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 699|回复: 5
收起左侧

[Leetcode] leercode_Wildcard Matching_dynamic programming

[复制链接] |试试Instant~ |关注本帖
415044809 发表于 2014-12-29 06:27:23 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 415044809 于 2014-12-29 07:53 编辑

非CS专业小白今日开始学习动态规划,遇到了这一题:
https://oj.leetcode.com/problems/wildcard-matching/
辛辛苦苦琢磨了三小时写出了代码,一跑却是
Submission Result: Time Limit Exceeded
为何动态规划还会超时呢?
求各位大神不吝赐教!跪谢!
我的代码:
  1. class Solution {
  2. public:
  3.     bool isMatch(const char *s, const char *p) {
  4.         if(s == NULL || p == NULL) return false;
  5.         int ls, lp;
  6.         for (ls = 0; *(s + ls) != '\0'; ls++); //count the length of s
  7.         for (lp = 0; *(p + lp) != '\0'; lp++); //count the length of p
  8.         if(ls == 0){                           // s == 0?
  9.             const char *tmp = p;
  10.             while(*tmp == '*') tmp++;
  11.             return *tmp == '\0';
  12.         }
  13.         if(lp == 0) return *s == '\0';         // p == 0?
  14.         
  15.         bool *a = new bool[lp]();
  16.         for (int i = 0; i < lp; i++) a[i] = true;
  17.         
  18.         bool *b = new bool[lp]();
  19.         for (int t = 0; t < ls; t++){
  20.             if(a[0] == true && *p == '*') b[0] = true;
  21.             else b[0] = false;
  22.             for (int j = 1; j < lp; j++){
  23.                 if((a[j] == true && *(p + j) == '*') || (a[j - 1] == true && (*(s + t) == *(p + j) || *(p + j) == '?'))) b[j] = true;
  24.                 else b[j] = false;
  25.             }
  26.             copy(a,b,lp);
  27.         }
  28.         return a[lp];
  29.     }
  30.     void copy(bool *a, bool *b, const int n){  
  31.         for(int i = 0; i < n; i++){
  32.             a[i] = b[i];
  33.         }
  34.     }      
  35. };
复制代码
犬座 发表于 2014-12-29 11:38:02 | 显示全部楼层
这题DP是O(mn), 大的test还是会超时。
  1. bool isMatch(const char *s, const char *p) {
  2.   if(!*p) return !*s;

  3.   char *astroid = NULL;
  4.   char *s1 = (char*)s;

  5.   while(*s) {
  6.     // match single character
  7.     if(*p == '?' || *p == *s) {
  8.       s++;
  9.       p++;
  10.       continue;
  11.     }

  12.     // meet an astroid, save its location and proceeds
  13.     if(*p == '*') {
  14.       astroid = (char*)p++;
  15.       s1 = (char*)s;
  16.       continue;
  17.     }

  18.     // backtrack
  19.     if(astroid) {
  20.       p = astroid + 1;
  21.       s = ++s1;
  22.       continue;
  23.     }

  24.     return false;
  25.   }

  26.   while(*p == '*') p++;
  27.   return !*p;
  28. }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| 415044809 发表于 2014-12-29 12:21:21 | 显示全部楼层
犬座 发表于 2014-12-29 11:38
这题DP是O(mn), 大的test还是会超时。

太谢谢啦!我要好好学学你的代码。能大体说一下backtrack大体是什么意思吗?
回复 支持 反对

使用道具 举报

犬座 发表于 2014-12-29 12:34:27 | 显示全部楼层
本帖最后由 犬座 于 2014-12-29 12:40 编辑
415044809 发表于 2014-12-29 12:21
太谢谢啦!我要好好学学你的代码。能大体说一下backtrack大体是什么意思吗?

s1记录的是离当前位置最近的*在s里match的最后一个位置

因为*能match任意长度的string, 所以只记录下离当前位置最近的*的位置,并在当前不match的时候回溯,看看之前有没有*。 有的话就从之前那个*在原s中match的最后一个位置之后的那个char开始继续match。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 415044809 发表于 2014-12-29 13:10:12 | 显示全部楼层
犬座 发表于 2014-12-29 12:34
s1记录的是离当前位置最近的*在s里match的最后一个位置

因为*能match任意长度的string, 所以只记录下 ...

大体看懂了。backtrack那块就是让*替代1个,2个,3个.....
还有一个小问题,就是觉得算法不太像动态规划...
回复 支持 反对

使用道具 举报

犬座 发表于 2014-12-29 13:14:27 | 显示全部楼层
415044809 发表于 2014-12-29 13:10
大体看懂了。backtrack那块就是让*替代1个,2个,3个.....
还有一个小问题,就是觉得算法不太像动态规划 ...

我的意思是你的DP解法是O(mn)不够快, 我给的是DFS =_=
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 00:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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