[LeetCode] Wildcard Matching

简介: Well, so many people has tried to solve this problem using DP. And almost all of them get TLE (if you see a C++ DP solution that gets accepted, please let me know ^_^).

Well, so many people has tried to solve this problem using DP. And almost all of them get TLE (if you see a C++ DP solution that gets accepted, please let me know ^_^). Well, this post aims at providing an accpted DP solution which uses a trick to get around the largest test case, insteaed of a solution that is fully correct. So please do not give me down votes for that :-)

Let's briefly summarize the idea of DP. We define the state P[i][j] to be whether s[0..i)matches p[0..j). The state equations are as follows:

  1. P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'), if p[j - 1] != '*';
  2. P[i][j] = P[i][j - 1] || P[i - 1][j], if p[j - 1] == '*'.

If you feel confused with the second equation, you may refer to this link. There is an explanation in the comments.

We optimize the DP code to O(m) space by recording P[i - 1][j - 1] using a single variablepre.

The trick to avoid TLE is to hard-code the result for the largest test case by

if (n > 30000) return false; 

The complete code is as follows.

 1 class Solution {
 2 public:
 3     bool isMatch(string s, string p) { 
 4         int m = s.length(), n = p.length();
 5         if (n > 30000) return false; // the trick
 6         vector<bool> cur(m + 1, false); 
 7         cur[0] = true;
 8         for (int j = 1; j <= n; j++) {
 9             bool pre = cur[0]; // use the value before update
10             cur[0] = cur[0] && p[j - 1] == '*'; 
11             for (int i = 1; i <= m; i++) {
12                 bool temp = cur[i]; // record the value before update
13                 if (p[j - 1] != '*')
14                     cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
15                 else cur[i] = cur[i - 1] || cur[i];
16                 pre = temp;
17             }
18         }
19         return cur[m]; 
20     }
21 };

For those interested in a fully correct solution, this link has a nice Greedy solution. And I have rewritten the code below to fit the new C++ interface (changed from char* to string).

 1 class Solution {
 2 public:
 3     bool isMatch(string s, string p) {
 4         int m = s.length(), n = p.length();
 5         int i = 0, j = 0, asterisk = -1, match;
 6         while (i < m) {
 7             if (j < n && p[j] == '*') {
 8                 match = i;
 9                 asterisk = j++;
10             }
11             else if (j < n && (s[i] == p[j] || p[j] == '?')) {
12                 i++;
13                 j++;
14             }
15             else if (asterisk >= 0) {
16                 i = ++match;
17                 j = asterisk + 1;
18             }
19             else return false;
20         }
21         while (j < n && p[j] == '*') j++;
22         return j == n;
23     }
24 };

 

目录
相关文章
|
索引 Python
LeetCode 44. Wildcard Matching
给定输入字符串s和模式串(p),实现通配符模式匹配支持'?' 和'*'.
73 0
LeetCode - 44. Wildcard Matching
44. Wildcard Matching  Problem's Link  ---------------------------------------------------------------------------- Mean:  给你一个字符串和一个自动机,问你自动机可否接收这个字符串.
1202 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
1月前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
1月前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积