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
思路:最大的难点在于:
ab|ef|cd|g|i|esc|de
ab|* |cd|?|i|*|de
这种匹配,即一个*不知道要匹配多少个字符,可能先匹配一个字符满足要求,但是后来的匹配过程中发现无法继续匹配时,需要回到*位置,匹配两个字符,再继续向前匹配,不断重复,直到匹配完全或者发现不能匹配。因此,对于每个*位置,需要记录下*的位置以及当时匹配的状态情况(类似于游戏中的复活点,可以saveloading)。
代码参考的Leetcode讨论区的高票答案。
class Solution {
public boolean isMatch(String s, String p) {
int i = 0;//尝试匹配 s
int j = 0;//尝试匹配 p
int resurgence = -1;//匹配失败时的复活点,即因为*的出现可能有多种长度的匹配,所以其中一种失败后
//p从“复活点”(上一个出现*的位置的状态)重新匹配,而s在复活点处对应的字符则可以由*匹配,即更换成另一种长度的匹配
int mark = 0;//记录下匹配到*时s对应的位置,用于“复活”(用*将s的当前字符串匹配掉)
while(i