Leetcode 44. Wildcard Matching

题目

44. Wildcard Matching

Difficulty: Hard
Total Accepted: 144.11K
Total Submissions: 665.07K

Given an input string (s) and a pattern (p), 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).

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:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

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

Example 4:

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

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

解题报告

AC 截图

题目大意

本题实际上是一个正则表达式的匹配问题，旨在检查字符串是否满足给定的正则表达式。正则表达式支持 ? 和 * 通配符，前者为单个字符的通配符，后者为任意字符序列（含空串）的通配符。

解题思路

对于此类状态转换，最暴力的做法自然是直接 DFS/BFS 扫描一遍看是否满足即可，但是这样的方法有很大的风险造成 TLE：

TLE 解

AC 截图

C++ 代码

class Solution {
public:
    bool isMatch(string s, string p) {
        return isMatchSubquestion(s, p);
    }
    
    bool isMatchSubquestion(string s, string p) {
        if (s.size() == 0) return 
            [&](){
            for (auto &i : p) if (i != '*') return false;
            return true;
        }();
        if (p.size() == 0) return s.size() == 0;
        switch(p[0]) {
            case '?' :
                return isMatchSubquestion(s.substr(1), p.substr(1));
            case '*' :
                return isMatchSubquestion(s.substr(1), p.substr(1)) ||
                    isMatchSubquestion(s.substr(1), p) ||
                    isMatchSubquestion(s, p.substr(1));
            default:
                return (s[0] == p[0]) && isMatchSubquestion(s.substr(1), p.substr(1));
        }
    }
};

题解分析

如你所见，暴力搜索的算法果然暴毙了（当然弱智的 substr 也得背锅），重复的 * 带来了难以忍受的时间复杂度，因而我们不得不考虑其他方法（或是想方法去除重复的 *，但是这不能改变暴力搜索效率低下的本质）。

让我们考虑这样一个回滚算法。我们首先尽可能多地匹配两个字符串，然后一旦遇到表达式中的 *，则记录该位置并跳过他继续匹配。如果后续不匹配，则从上一个 * 位置之后的第 i 个位置继续匹配（i 为不匹配的次数），直到遍历完字符串或者表达式为止。

写作代码如下：

题解1（最优解）

C++ 代码

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    bool isMatch(string& s, string& p) {
        int sIndex = 0, pIndex = 0;
        int pStarIndex = -1, sStarIndex = -1;
        int sSize = s.size();
        while (sIndex < sSize) {
            if (s[sIndex] == p[pIndex] || p[pIndex] == '?') {
                ++sIndex;
                ++pIndex;
            }
            else if (p[pIndex] == '*') {
                pStarIndex = pIndex++;
                sStarIndex = sIndex;
            }
            else if (pStarIndex > -1){
                pIndex = pStarIndex + 1;
                sIndex = ++sStarIndex;
            }
            else
                return false;
        }
        while(p[pIndex] == '*') ++pIndex;
        return (pIndex == p.size());
    }
};