LintCode 通配符匹配

本文主要是介绍LintCode 通配符匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考资料
判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。

两个串完全匹配才算匹配成功。

函数接口如下:
bool isMatch(const char *s, const char *p)

一些例子：

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

先对题目说明一下，题目的意思应该是通配符只出现在一个串中。Accepted之后，我试了一下ab*ade与abcd*e这两个串，期望结果是False，但这两个串的应该是可以匹配的。

动态规划。
dp[i , j]表示s串的前i个字符与p串的前j个字符的匹配情况。假设通配符只出现在p串中，首先dp[0 , 0]=1.dp[0 , j]只有在p[j]=*的时候才为True。dp[i , 0]均为False。
其他情况：
1. s[i]==p[j] 或 p[j]==?：dp[i , j]=dp[i-1 , j-1]
2. p[j]==* : 需要查看p串中“*”前的字符串p[0…j-1]能否与s[0…i]中的前某一部分子串匹配，若能，可以用星号代替其余的子串，即为可以匹配，dp[i ,j ]=True.那么也就是查看 dp[0…i , j-1]中是否有true。这里需要注意：并不能认为只需要查看s串中长度大于等于j-1的子串，即不能认为只需要查看dp[j-1…i , j-1]中是否有true。因为p串中在之前也可能出现星号。看下面这个例子：
s串：abcfde p串：a*bc*e
当s[i]=”d” , p[j]=第二个星号时，若只查看dp[4 , 4 ]和dp[5 , 4],均为false，那么会得到错误结论，dp[5 , 5]=false，实际上,abcfd和a*bc*是可以匹配的。
代码如下：

class Solution:"""@param: s: A string @param: p: A string includes "?" and "*"@return: is Match?"""def isMatch(self, s, p):# write your code herem=len(s)n=len(p)dp=[[False]*(n+1) for x in range(m+1)]dp[0][0]=Truefor i in range(1,n+1):if p[i-1]=='*':dp[0][i]=True and dp[0][i-1]for i in range(1,m+1):for j in range(1,n+1):if s[i-1]==p[j-1] or p[j-1]=='?':dp[i][j]=dp[i-1][j-1]elif p[j-1]=='*':for k in range(0,i+1):if dp[k][j-1]==True:dp[i][j]=Truebreakreturn dp[m][n]