请问LeetCode Wild Matching的贪心解法，为什么只需要记录最后一个*? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请问LeetCode Wild Matching的贪心解法，为什么只需要记录最后一个*?

请问LeetCode Wild Matching的贪心解法，为什么只需要记录最后一个*?# JobHunting - 待字闺中

s*p2014-10-11 07:10

1 楼

就是这题：
https://oj.leetcode.com/problems/wildcard-matching/
一直没有想明白，为什么只需要记录最后一次的*的位置，而不用管前面的*。在网上搜
了也没有找到关于这方面的解答的。
有谁能帮忙解释下？非常感谢！

b*02014-10-11 07:10

2 楼

我是这么想的
如果更前面的*匹配到当前字符的话
那我一样可以用最后一次的*来匹配到当前字符

j*g2014-10-11 07:10

3 楼

这个算法的核心思想是检查p中*字符之间的字符是否在s中有相应的匹配。一旦遇到第
二个*字符，说明第一个*字符和第二个*字符之间的字符已经得到了匹配。继续检验第
二个*字符和第三个*字符是否在s中有相应的匹配。所以不需要记录前面第一个*的位置
了。
[在 sodcap (sodcap) 的大作中提到：]
：就是这题：
：
：...........

s*p2014-10-11 07:10

4 楼

可是p两个*之前的字符串可能在s中有多个匹配。为什么在s中有了匹配，就不需要退回
到前面去了？

p*y2014-10-11 07:10

5 楼

因为除了第一个匹配的p必须要有之外，其他的第二个*都能cover了。
很绕人的

【在 s****p 的大作中提到】

: 可是p两个*之前的字符串可能在s中有多个匹配。为什么在s中有了匹配，就不需要退回
: 到前面去了？

n*12014-10-11 07:10

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