Wildcard Matching
Implement wildcard pattern matching with support for ‘?’ and ‘*’.
Example:
'?' 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
My Solution
Use the Dynamic Programme. Use the same method as “010. Regular Expression Matching”. Use the new matrix dp[i][j]. Its value equals to the matching situation of first i items in s and first j items in p.
Firstly we set all the value in dp as False. If the matching situation is acceptable, change situation from False to True. And finally we need the dp[len(s)][len(p)].
The next step of Dynamic Programme is we need to find the recursive function. We can set the rules as follows.
If the i equals to 0, if p[j-1] equals to "*", then next p[j] will have the same status as p[j-1].
If the i in range 1 to len(s), there are several situations.
1. If s[i-1] == p[j-1] or p[j-1] is ".", the True status will delivery to lower right conrner.
2. If p[j-1] is "*", the True status will delivery to bottom of it, and all the right of the bottom one.
3. Otherwise the True status will not delivery.
With this two kinds of rules, we can give the final solution.
Python code
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
dp = [[False for _ in range(len(p)+1)] for _ in range(len(s)+1)]
dp[0][0] = True
if len(s) == 0 and len(p) == 1 and p[0] == "*": return True
for j in range(1,len(p)+1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for j in range(1,len(p)+1):
for i in range(1,len(s)+1):
if p[j-1] == "*":
dp[i][j] = ((dp[i-1][j-1] or dp[i-1][j]) and i > 0) or dp[i][j-1]
elif p[j-1] == s[i-1] or p[j-1] == "?":
dp[i][j] = dp[i-1][j-1] and i > 0
return dp[len(s)][len(p)]
近期评论