题目：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

用‘？’和‘*’来匹配字符串，‘？’可以匹配任意一个字符，’*’可以匹配任意一串序列（包括空串）。只有整个字符串都匹配成功才能算是匹配成功。 例： 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，长度分别为len1和len2。 用两个指针i,j分别指向s和p当前比较的元素。 如果s[i] == p[j]或者p[j] == ‘?’的话，表示当前位置匹配成功，i和j分别指向下一个位置。 如果p[j] == ‘*’的话，记录当前i（假设为index）和j（假设为starPos）的位置，并把j指向下一个位置（就是默认*代表一个空串）。 如果当前位置的匹配不成功的话，回退到之前的*号的位置，让*号代表的字符串多增加一位(例：之前是让*代表一个空串，这次让*代表子串s[index…]),然后重新让i == ++index, j = starPos + 1开始匹配。 如果还不成功，则无法匹配成功。

代码如下：

class Solution { public: bool isMatch(string s, string p) { int len1 = s.length(), len2 = p.length(); int i = 0, j = 0, starPos = -1, index; while(i < len1){ if(j < len2 && (s[i] == p[j] || p[j] == '?')){ i++, j++; }else if(j < len2 && p[j] == '*'){ starPos = j++; index = i; }else if(starPos >= 0){ i = ++index; j = starPos + 1; }else{ return false; } } while(j < len2 && p[j] == '*') j++; return j == len2; } };