Question: https://oj.leetcode.com/problems/wildcard-matching/
Question Name: Wildcard Matching
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | class Solution: # @param p, the original pattern string # @return, a compressed pattern string, and the minimal number of characters # in a matching string. def _compile(self, p): # Handle with a special case that the pattern string is empty if len(p) == 0: return "", 0 result = p[0] # Compressed pattern minimal = 0 # Minimal number of chars in any matching string for i in p[1:]: # Count the minimal number of chars if i!= "*": minimal += 1 # Compress consecutive stars into one if i == "*" and i == result[-1]: continue else: result += i return result, minimal # @param s, an input string # @param sIndex, the begin position of s to check # @param p, a pattern string # @param pIndex, the begin position of p to match # @return a boolean def _isMatchHelper(self, s, sIndex, p, pIndex, tried): while True: # Cache the previous failure if tried[sIndex] & (1<<pIndex) != 0: return False else: tried[sIndex] |= (1<<pIndex) # Both input and pattern have nothing left. Match success! if sIndex == len(s) and pIndex == len(p): return True # Either the input has something unmatched elif pIndex == len(p): return False # In the pattern, only one star is left. It matches every string. elif pIndex == len(p) - 1 and p[pIndex] == "*": return True # Single character matches. elif sIndex != len(s) and (p[pIndex] == "?" or s[sIndex] == p[pIndex]): sIndex += 1 pIndex += 1 # Deal with star match elif p[pIndex] == "*": # "*" means empty string if self._isMatchHelper(s, sIndex, p, pIndex+1, tried): return True # "*" consume one character elif sIndex != len(s) and self._isMatchHelper(s, sIndex+1, p, pIndex, tried): return True # No way to match "*" else: return False # input and pattern do not match for current position. Fails. else: return False # @param s, an input string # @param p, a pattern string # @return a boolean def isMatch(self, s, p): p, mininal = self._compile(p) # Not enough characters in s to be matched for pattern p if mininal > len(s): return False else: tried = [0 for _ in xrange(len(s)+1)] return self._isMatchHelper(s, 0, p, 0, tried) |