"""
@href: https://leetcode.com/problems/wildcard-matching/description/
@title: 44. Wildcard Matching
"""
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
ls, lp =
len(s), len(p)
if (ls + lp) ==
0:
return True
s, p =
'a' + s,
'a' +
p
ls, lp = ls+1, lp+1
dp = [[False]*(lp+1)
for i
in range(0, ls+1
)]
dp[0][0] =
True
for i
in range(1, ls+1
):
for j
in range(1, lp+1
):
if p[j-1] == s[i-1]
or p[j-1]
in '?*':
dp[i][j] = dp[i-1][j-1
]
if p[j-1] ==
'*':
dp[i][j] = dp[i][j]
or dp[i-1][j]
or dp[i][j-1
]
else:
if p[j-1] ==
'*':
dp[i][j] = dp[i][j-1
]
return dp[ls][lp]
我用的是二维 dp， 有人给出了 一维 dp 解法
转载于:https://www.cnblogs.com/tmortred/p/8038874.html
