点击刷新
192. 通配符匹配
中文
English
判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：
- '?' 可以匹配任何单个字符。
- '*' 可以匹配任意字符串（包括空字符串）。
两个串完全匹配才算匹配成功。
样例
样例1
输入:
"aa"
"a"
输出: false
输出2
输入:
"aa"
"aa"
输出: true
输出3
输入:
"aaa"
"aa"
输出: false
输出4
输入:
"aa"
"*"
输出: true
说明: '*' 可以替换任何字符串
输出5
输入:
"aa"
"a*"
输出: true
样例6
输入:
"ab"
"?*"
输出: true
说明: '?' -> 'a' '*' -> 'b'
样例7
class Solution:
"""
@param s: A string
@param p: A string includes "?" and "*"
@return: is Match?
"""
def isMatch(self, s, p):
# write your code here
m,n = len(s),len(p)
dp = [[False]*(n+1) for i in range(m+1)]
dp[0][0] = True
for i in range(1, m+1):
dp[i][0] = False
for j in range(1, n+1):
dp[0][j] = dp[0][j-1] and p[j-1] == '*'
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] == '*':
dp[i][j] = dp[i-1][j-1] or dp[i][j-1] or dp[i-1][j]
else:
dp[i][j] = dp[i-1][j-1] and (p[j-1] == '?' or p[j-1] == s[i-1])
return dp[m][n]
"""
def dfs(s, i, p, j):
if i == len(s) and j == len(p):
return True
if i == len(s) and p[j:] == "*":
return True
if i == len(s) or j == len(p):
return False
if p[j] == '?':
return dfs(s, i+1, p, j+1)
elif p[j] == '*':
return dfs(s, i, p, j+1) or dfs(s, i+1, p, j+1) or dfs(s, i+1, p, j)
else:
if s[i] != p[j]:
return False
return dfs(s, i+1, p, j+1)
return dfs(s, 0, p, 0)
"""
154. 正则表达式匹配
中文
English
实现支持'.'和'*'的正则表达式匹配。
'.'匹配任意一个字母。
'*'匹配零个或者多个前面的元素。
匹配应该覆盖整个输入字符串，而不仅仅是一部分。
需要实现的函数是：bool isMatch(string s, string p)
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
样例
样例 1:
输入："aa"，"a"
输出：false
解释：
无法匹配
样例 2:
输入："aa"，"a*" 输出：true 解释： '*' 可以重复 a
class Solution:
"""
@param s: A string
@param p: A string includes "." and "*"
@return: A boolean
"""
def isMatch(self, s, p):
# write your code here
m, n = len(s), len(p)
dp = [[False] * (n + 1) for i in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = False
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
continue
if j < n and p[j - 1] != '*' and p[j] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 1]
continue
if j < n and p[j] == '*':
if p[j-1] != '.' and p[j - 1] != s[i - 1]:
dp[i][j] = dp[i][j - 1]
else:
dp[i][j] = dp[i][j - 1] or dp[i - 1][j - 1] or dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j - 1] and (p[j - 1] == '.' or p[j - 1] == s[i - 1])
return dp[m][n]
© 著作权归作者所有
举报
发表评论
0/200
