Leetcode(44) Wildcard Matching

发表于 | 分类于

Description

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

1
2
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
4
5
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

1
2
3
4
5
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

1
2
3
4
5
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

1
2
3
4
Input:
s = "acdcb"
p = "a*c?b"
Output: false

解法

这道题花的时间挺久，主要是思路难理顺。算法采用的是回溯算法，由题意，？匹配任意一个字符，*匹配任意字符串，我们先考虑采取指针pcur和scur分别指向当前待匹配的字符，那么在匹配过程中，会碰到如下几种情况：

情况1：p[pcur] = s[scur] or p[cur] = ‘?’

匹配成功，pcur和scur分别加一指向下一个字符

情况2：p[pcur] = ‘*‘

这个时候就想着怎么在s中寻找与*配对的字符串，匹配多少个成了需要考虑的问题，那么我们不妨从匹配0个开始尝试，如果匹配0个以后后续字符串出现了无法匹配的情况，则回到星号的位置重新进行匹配，尝试匹配个数比上一次多一个的匹配。为了达到此目的，我们需要添加两个指示量:pstar指向p中*的位置，sstar指向s中下一个*可以匹配的字符位置。

于是情况的划分可变为：

情况1：p[pcur] = s[scur] or p[cur] = ‘?’

匹配成功，pcur和scur分别加一指向下一个字符

情况2：p[pcur] = ‘*‘

记录pstar与sstar的位置，并默认匹配0个字符，所以pcur需要+1而scur保持不变

情况3：以上两种情况都不满足，但是之前有过*号，那么说明按照之前的方法匹配出现了问题，需要重新考虑*号的匹配问题，将*号匹配的字符串长度+1,重新将pcur指向*号后的下一个字符，sstar+1,然后将s中待匹配的下一个字符设为现在的sstar值。

具体代码如下：

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
33
34
35
36
37
38
39
class Solution {
    public boolean isMatch(String s, String p) {
        int scur = 0;
        int pcur = 0;
        int sstar = 0;
        int pstar = -1;
        while (scur < s.length()) {
            //相当或问号的情况
            if (pcur < p.length() && (p.charAt(pcur) == s.charAt(scur) || p.charAt(pcur) == '?')) {
                pcur++;
                scur++;
            }
            //碰到了星号，pstar记录星号位置，sstar记录星号可以匹配的下一个字符的位置，初始情况星号匹配0个字符
            else if (pcur < p.length() && p.charAt(pcur) == '*') {
                pstar = pcur;
                sstar = scur;
                pcur++;
            }
            //这个时候匹配出现问题了，因为不满足以上两种情况，所以考虑对星号的处理，星号比上一次多匹配一个字符
            //将下一个待匹配的p字符设为*后的第一个字符，sstar+1（就是比上一次多匹配一个的意思)，scur设为下一个待匹配的s字符
            else if (pstar != -1) {
                pcur = pstar + 1;
                sstar++;
                scur = sstar;
            } else {
                return false;
            }
        }
        //处理结尾的多余*号
        while (pcur < p.length()) {
            if (p.charAt(pcur) == '*') {
                pcur++;
            } else {
                return false;
            }
        }
        return true;
    }
}