44. Wildcard Matching Leetcode Python

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

class Solution:
    # @param s, an input string
    # @param p, a pattern string
    # @return a boolean
    ## example s = aa p = *
    # start will maintain the position and i will increase
    def isMatch(self, s, p):
        i = 0
        j = 0
        sstar = 0
        star = -1
        while i < len(s):
            ## first case compare ? or whether they are exactly the same
            if j < len(p) and (s[i] == p[j] or p[j] == '?'):
                i += 1
                j += 1
            ## if there is a * in p we mark current j and i    
            elif j < len(p) and p[j] == '*':
                star = j
                j += 1
                sstar = i
            ## if current p[j] is not * we check whether prior state has *
            elif star != -1:
                j = star + 1 
                sstar += 1
                i = sstar
            else:
                return False
        while j < len(p) and p[j] == '*':
            j += 1
        if j == len(p):
            return True
        return False

44. Wildcard Matching Leetcode Python

原文：http://blog.csdn.net/hyperbolechi/article/details/44670659