44. Wildcard Matching（通配符匹配）

• Wildcard Matching通配符匹配
  • 题目链接
  • 题目描述
  • 题目分析
    • 方法贪心
      • 算法描述
  • 参考代码

题目链接

https://leetcode.com/problems/wildcard-matching/description/

题目描述

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”, “c*a*b”) → false

题目分析

这道题目中只有两种通配符，所以并不算是太复杂。

？

只能匹配1个字符，基本没有什么问题。主要的问题在于

*

匹配多长的串合适。经过分析，可以发现：必须让每个

*

匹配尽量短的字符串。试想，若

*

匹配的串过长，例如

"zacabaz"

和

"*ac*"

匹配，第1个

*

只能匹配一个

z

，否则会得到不能匹配。

方法：贪心

算法描述

设待匹配的字符串为

S

，表达式为

P

。

i

为

S

的下标，

j

为

P

的下标。

wildcard

为最后一次出现的

*

下标。

1. 若

S[i]

可以和

P[i]

匹配（

S[i] == P[i]

或

P[i] == '?'

)，

i

和

j

都加

1

2. 若

P[i] == '*'

，

wildcard

指向

j

所指向的位置，

i

和

j

都加

1

3. 若

S[i]

无法和

P[i]

匹配，则必须用

*

匹配到此位置。

j = wildcard + 1

，

i++

参考代码

class Solution {
public:
    bool isMatch(string s, string p) {
        string temp;
        for (int i = ; i < p.size(); i++) {
            if (p[i] == '*' && i >  && p[i - ] == '*')
                continue;
            temp.push_back(p[i]);
        }
        p = temp;

        int i = , j = , wildcard = -, match;
        while (i < s.size()) {
            if (j < p.size() && p[j] == '*') {
                match = i;
                wildcard = j++;
            }
            else if (j < p.size() && (s[i] == p[j] || p[j] == '?')) {
                i++;
                j++;
            }
            else if (wildcard >= ) {
                i = ++match;
                j = wildcard + ;
            }
            else
                return false;
        }
        if (j < p.size() && p[j] == '*') j++;
        return j == p.size();
    }
};