Wildcard Matching

Question

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

Thoughts

这一题跟regular expression差不多，只是*的性质变了，不再跟之前的一个char有关

要改动的点

• "*" 可以在第一个
• 最后p[j-1] == "*"的状况

Solution

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

        dp = [[False for j in range(lenP+1)] for i in range(lenS+1)]
        dp[0][0] = True

        for i in range(lenS + 1):
            for j in range(1, lenP + 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] == "?":
                    if dp[i-1][j-1]:
                        dp[i][j] = True
                else:
                    if dp[i-1][j]:
                        dp[i][j] = True
                    if dp[i][j-1]:
                        dp[i][j] = True

        return dp[lenS][lenP]