44. Wildcard Matching

发表于 | 分类于

Implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char s, const char p)

Some examples:
isMatch(“aa”,”a”) ? false
isMatch(“aa”,”aa”) ? true
isMatch(“aaa”,”aa”) ? false
isMatch(“aa”, ““) ? true
isMatch(“aa”, “a“) ? true
isMatch(“ab”, “?“) ? true
isMatch(“aab”, “ca*b”) ? false

解法1：

这题的关键在于对于*的处理。
DP 不能过OJ
two pointers可以，关键思路是碰到＊先从match 0个字符开始，往后继续match，如果发现不match了那就试着match 1个字符，以此类推。
最后要注意是否pattern还只剩＊
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null && p == null) return true;
        if (s == null || p == null) return false;
        int ss = 0, pp = 0, starIndex = -1, match = 0;
        while (ss < s.length()) {
            if (pp < p.length() && (s.charAt(ss) == p.charAt(pp) || p.charAt(pp) == '?')) {
                ss++;
                pp++;
            } else if (pp < p.length() && p.charAt(pp) == '*') {
                starIndex = pp;
                match = ss;
                pp++;
            } else if (starIndex != -1) {
                pp = starIndex + 1;
                match++;
                ss = match;
            } else {
                return false;
            }
        }
        while (pp < p.length() && p.charAt(pp) == '*') {
            pp++;
        }
        return pp == p.length();
    }
}