Wildcard Matching

Question

• leetcode: Wildcard Matching | LeetCode OJ
• lintcode: (192) 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).

Example
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

题解1 - DFS

字符串的通配实现。'?'表示匹配单一字符，'*'可匹配任意多字符串(包含零个)。要匹配的字符串设为s, 模式匹配用的字符串设为p，那么如果是普通字符，两个字符串索引向前推进一位即可，如果p中的字符是?也好办，同上处理，向前推进一位。所以现在的关键就在于如何处理'*', 因为*可匹配0, 1, 2...个字符，所以遇到*时，s应该尽可能的向前推进，注意到p中*后面可能跟有其他普通字符，故s向前推进多少位直接与p中*后面的字符相关。同时此时两个字符串的索引处即成为回溯点，如果后面的字符串匹配不成功，则s中的索引向前推进，向前推进的字符串即表示和p中*匹配的字符个数。

• reference
• visualization

class Solution:
    """
    @param s: A string 
    @param p: A string includes "?" and "*"
    @return: A boolean
    """
    def isMatch(self, s, p):
        # write your code here

        n = len(s)
        m = len(p)
        f = [[False]*(m+1) for i in range(n+1)]
        f[0][0] = True

        for i in range(1, n+1):
            for j in range(1, m+1):
                f[i][j] = (
                    (f[i-1][j-1] and
                    (s[i-1] == p[j-1] or p[j-1] == '?' or p[j-1] == '*')) or
                    f[i-1][j] and p[j-1] == '*')

        return f[n][m]

题解2

• reference
• visualization

class Solution:
    # @param s, an input string
    # @param p, a pattern string
    # @return a boolean
    # @good solution! use 'aaaabaaaab' vs 'a*b*b' as an example
    def isMatch(self, s, p):
        pPointer=sPointer=ss=0; star=-1
        while sPointer<len(s):
            if pPointer<len(p) and (s[sPointer]==p[pPointer] or p[pPointer]=='?'):
                sPointer+=1; pPointer+=1
                continue
            if pPointer<len(p) and p[pPointer]=='*':
                star=pPointer; pPointer+=1; ss=sPointer;
                continue
            if star!=-1:
                pPointer=star+1; ss+=1; sPointer=ss
                continue
            return False
        while pPointer<len(p) and p[pPointer]=='*':
            pPointer+=1
        if pPointer==len(p): return True
        return False