leetcode筆記：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", "c*a*b") → false

二. 題目分析

題目的大意是，給出兩串字符串s和p，規定符號?能匹配任意單個字符，*能匹配任意字符序列（包括空字符序列）。如果兩串字符串完全匹配則返回true。

該題的難點主要在於出現*時的匹配操作。和網上大多數做法相似，一開始使用遞歸完成，結果總是超時。後來使用幾個變量用於記錄遇到p中的*時的下標，每次遇到一個*，就保留住當前字符串s和p的下標，然後s從當前下標往後掃描，如果不匹配，則s的下標加一，重復掃描。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int s_size = s.size();
        int p_size = p.size();
        int s_index = 0, p_index = 0;
        int temp_s_index = -1, temp_p_index = -1;
        while (s_index < s_size)
        {
            if (p[p_index] == '?' || p[p_index] == s[s_index])
            {
                ++p_index;
                ++s_index;
                continue;
            }
            if (p[p_index] == '*') 
            {
                temp_p_index = p_index;
                temp_s_index = s_index;
                ++p_index;
                continue;
            }
            if (temp_p_index >= 0)
            {
                // 字符串p可能有多個*，因此只要出現過*，則需要更新當前匹配的下標
                p_index = temp_p_index + 1;
                s_index = temp_s_index + 1;
                // 當前坐標s與p不匹配，則s的坐標在原基礎上加一，繼續循環
                ++temp_s_index; 
                continue;
            }
            return false;
        }
        while (p[p_index] == '*') ++p_index;
        return p_index == p_size;
    }
};

四. 小結

這種題目一般遞歸的思路還是首選，但遞歸的最大缺點就是耗時。該題若使用動態規劃也可以解決，但是未必能達到以上方法的