**一. 題目描述** 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 <iostream> #include <string> 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; } }; ~~~ **四. 小結** 這種題目一般遞歸的思路還是首選，但遞歸的最大缺點就是耗時。該題若使用動態規劃也可以解決，但是未必能達到以上方法的