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

解题方法

backtracking + dfs

和regular expression的做法差不多，转变一下*的处理情况

DP

首先我们想到这一题和regular rexpression matching差不多，也可以用DP来解，主要就是将"*"的情况改变一下

two pointer

上面两种做法都过不了leetcode,因为time limit和stack limit，我们只能另想办法。看了各路大神的解法，找到了将 recursive改为two-pointer的做法，思路还是遇到*时不断从0个开始往后试探匹配，如果不行的话就回朔，关键就是 回朔时候的pointer reset到哪里的问题。

pointer reset到哪里的问题

  • 首先我们有两个pointer分别对应s和p

当处理*时，我们需要从匹配0个开始不断地试探匹配，当匹配不成功的话，我们就应该回朔，尝试再用*多匹配 一位继续尝试看是否能够成功，这个reset的过程我们对两个Pointer都要reset

  • 假如我们上一次已经尝试用*匹配了n个字符，那么s的pointer应该设置到上一次匹配n个字符的后一位
  • 而p的pointer呢，我们应该还是从*后面开始新一次的尝试

所以我们要有两个变量

  • star记录*出现的位置
  • lastMatch记录上一次对s匹配到的位置

而根据这个文章分析，我们只需要回去尝试最后一个*就可以。

Solution

DP

超时

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if len(p) == 0:
            return len(s) == 0

        lengthS = len(s)
        lengthP = len(p)

        dp = [[False for i in range(lengthP + 1)] for j in range(lengthS + 1)]

        dp[0][0] = True

        # init state, match no characters
        # last char in pattern has to be "*", which match 0 characters
        for i in range(1, lengthP + 1):
            if p[i-1] == "*":
                dp[0][i] = True
            else:
                break

        for i in range(1, lengthS + 1):
            for j in range(1, lengthP + 1):
                if p[j-1] != "?" and p[j-1] != "*":
                    if dp[i-1][j-1] and s[i-1] == p[j-1]:
                        dp[i][j] = True
                elif p[j-1] == "?":
                    dp[i][j] = dp[i-1][j-1]
                else: # "*" can't be first char
                    if dp[i][j-1]:
                        # match 0
                        dp[i][j] = True
                    elif dp[i-1][j-1]:
                        # match 1
                        dp[i][j] = True
                    elif dp[i-1][j]:
                        # match 2+, 往前退回
                        dp[i][j] = True

        return dp[lengthS][lengthP]

backtracking + dfs

def isMatch(self, s, p):
        # write your code here
        if len(p) == 0: return len(s) == 0

        if p[0] != "*":
            if len(s) == 0 or (s[0] != p[0] and p[0] != "?"):
                return False
            return self.isMatch(s[1:], p[1:])
        else:
            for i in range(0, len(s)+1):
                if self.isMatch(s[i:], p[1:]):
                    return True

        return False

Two-pointer 做法

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        pI = 0
        sI = 0
        lastMatch = -1
        star = -1

        while sI < len(s):
            if pI < len(p) and (p[pI] == "?" or p[pI] == s[sI]):
                # 当是"?"或者是匹配字符时，不要考虑别的，直接都往后一位
                pI += 1
                sI += 1
            elif pI < len(p) and p[pI] == "*":
                # 当是 * 的时候， 就应该从匹配0个开始尝试
                # start 记录 * 的位置以便下次reset
                # lastMatch 设为当前匹配到的s的位置
                # 只前进p的指针，表示先尝试对s匹配0个
                star = pI
                lastMatch = sI
                pI += 1
            elif star != -1:
                # 前面都没有满足或者j已经超出范围了，无法匹配了，就应该重设了
                # p的指针重设到*的后面
                # s的指针重设到上一次尝试匹配n个字符的后一个
                pI = star + 1
                lastMatch += 1
                sI = lastMatch
            else:
                # 没有*,已经无法匹配，直接返回 False
                return False

        # 如果p的指针还没有到底的话，只能是将*的跳过
        while pI < len(p) and p[pI] == "*":
            pI += 1

        # 如果p的指针后面还有多余的非*的字符，说明无法匹配
        # 如果到底了，说明成功匹配
        return pI == len(p)

Reference