s****p
发帖数: 124 | 1 就是这题：
https://oj.leetcode.com/problems/wildcard-matching/
一直没有想明白，为什么只需要记录最后一次的*的位置，而不用管前面的*。在网上搜
了也没有找到关于这方面的解答的。
有谁能帮忙解释下？非常感谢！ |
b********0
发帖数: 62 | 2 我是这么想的
如果更前面的*匹配到当前字符的话
那我一样可以用最后一次的*来匹配到当前字符 |
j**********g
发帖数: 77 | 3 这个算法的核心思想是检查p中*字符之间的字符是否在s中有相应的匹配。一旦遇到第
二个*字符，说明第一个*字符和第二个*字符之间的字符已经得到了匹配。继续检验第
二个*字符和第三个*字符是否在s中有相应的匹配。所以不需要记录前面第一个*的位置
了。
[在 sodcap (sodcap) 的大作中提到：]
：就是这题：
：
：........... |
s****p
发帖数: 124 | 4 可是p两个*之前的字符串可能在s中有多个匹配。为什么在s中有了匹配，就不需要退回
到前面去了？ |
p***y
发帖数: 637 | 5 因为除了第一个匹配的p必须要有之外，其他的第二个*都能cover了。
很绕人的
【在 s****p 的大作中提到】
: 可是p两个*之前的字符串可能在s中有多个匹配。为什么在s中有了匹配，就不需要退回
: 到前面去了？
|
n****1
发帖数: 1136 | 6 有没有人用python写啊? 我写的老超时。请大家指教
class Solution:
def isMatch(self, s, p):
p2 = ""
while p != p2: #Remove duplicate *
p2 = p
p = p.replace("**","*")
ls = len(s)-1
lp = len(p)-1
old_states = {-1}
for s_ptr in range(ls +1):
new_states = set();
for p_ptr in old_states:
if p_ptr >= lp:
return False
if ( p[p_ptr+1] == s[s_ptr] or p[p_ptr+1] == '?' or p[p_ptr+1]
== '*' ):
new_states.add(p_ptr+1)
if p_ptr > -1 and p[p_ptr] == '*':
new_states.add(p_ptr)
old_states = new_states
if lp in old_states:
return True
else:
return False |
