[LintCode]ワイルドカードクエリ
9076 ワード
動的計画:
欲張り:
1 class Solution {
2 public:
3 /**
4 * @param s: A string
5 * @param p: A string includes "?" and "*"
6 * @return: A boolean
7 */
8 bool isMatch(const char *s, const char *p) {
9 // write your code here
10 int m = strlen(s), n = strlen(p);
11 vector<bool> cur(m + 1, false);
12 cur[0] = true;
13 for (int j = 1; j <= n; j++) {
14 bool pre = cur[0];
15 cur[0] = cur[0] && p[j - 1] == '*';
16 for (int i = 1; i <= m; i++) {
17 bool temp = cur[i];
18 if (p[j - 1] != '*')
19 cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
20 else cur[i] = cur[i - 1] || cur[i];
21 pre = temp;
22 }
23 }
24 return cur[m];
25 }
26 };
欲張り:
1 class Solution {
2 public:
3 /**
4 * @param s: A string
5 * @param p: A string includes "?" and "*"
6 * @return: A boolean
7 */
8 bool isMatch(const char *s, const char *p) {
9 // write your code here
10 const char* asterisk = NULL;
11 const char* match = NULL;
12 while (*s) {
13 if (*p == '*') {
14 asterisk = p++;
15 match = s;
16 }
17 else if (*s == *p || *p == '?') {
18 s++;
19 p++;
20 }
21 else if (asterisk) {
22 s = ++match;
23 p = asterisk + 1;
24 }
25 else return false;
26 }
27 while (*p == '*') p++;
28 return !*p;
29 }
30 };