leercode_Wildcard Matching_dynamic programming

非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. };

复制代码

这题DP是O(mn), 大的test还是会超时。

1. bool isMatch(const char *s, const char *p) {
   
2.   if(!*p) return !*s;
   
3. 
   
4.   char *astroid = NULL;
   
5.   char *s1 = (char*)s;
   
6. 
   
7.   while(*s) {
   
8.     // match single character
   
9.     if(*p == '?' || *p == *s) {
   
10.       s++;
    
11.       p++;
    
12.       continue;
    
13.     }
    
14. 
    
15.     // meet an astroid, save its location and proceeds
    
16.     if(*p == '*') {
    
17.       astroid = (char*)p++;
    
18.       s1 = (char*)s;
    
19.       continue;
    
20.     }
    
21. 
    
22.     // backtrack
    
23.     if(astroid) {
    
24.       p = astroid + 1;
    
25.       s = ++s1;
    
26.       continue;
    
27.     }
    
28. 
    
29.     return false;
    
30.   }
    
31. 
    
32.   while(*p == '*') p++;
    
33.   return !*p;
    
34. }
    

复制代码

犬座 发表于 2014-12-29 11:38
这题DP是O(mn), 大的test还是会超时。

太谢谢啦！我要好好学学你的代码。能大体说一下backtrack大体是什么意思吗？

415044809 发表于 2014-12-29 12:21
太谢谢啦！我要好好学学你的代码。能大体说一下backtrack大体是什么意思吗？

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

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

犬座 发表于 2014-12-29 12:34
s1记录的是离当前位置最近的*在s里match的最后一个位置

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

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

415044809 发表于 2014-12-29 13:10
大体看懂了。backtrack那块就是让*替代1个，2个，3个.....
还有一个小问题，就是觉得算法不太像动态规划 ...

我的意思是你的DP解法是O(mn)不够快, 我给的是DFS =_=