由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请问LeetCode Wild Matching的贪心解法,为什么只需要记录最后一个*?
相关主题
问一道Leetcode的题目。Leetcode regular expression 问题
问一道LeeCode题目: regular expression matchingjava没有指针真麻烦
问一下 leetcode里面的 regular expression matching问个算法问题
Leetcode regular expression matching那道题问个google老题的最佳解法
Leetcode-010: Regular Expression Match (DP Solution)leetcode 上面的Regular Expression Matching
Leetcode WildCard Matching这个字符串题有什么好的解法?
Wildcard Matching 和 Regular Expression Matching 区别是什么Wildcard Matching题求助
Leetcode TimeoutRegular Expression Matching 问题请教。。
相关话题的讨论汇总
话题: ptr话题: states话题: 字符话题: old话题: p2
进入JobHunting版参与讨论
1 (共1页)
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
1 (共1页)
进入JobHunting版参与讨论
相关主题
Regular Expression Matching 问题请教。。Leetcode-010: Regular Expression Match (DP Solution)
isMatch("ab", ".*") → true 为什么是true???Leetcode WildCard Matching
leetcode中那道Set Matrix Zeroes怎么做Wildcard Matching 和 Regular Expression Matching 区别是什么
ValidNumber实在是不能不服如此简洁的解法Leetcode Timeout
问一道Leetcode的题目。Leetcode regular expression 问题
问一道LeeCode题目: regular expression matchingjava没有指针真麻烦
问一下 leetcode里面的 regular expression matching问个算法问题
Leetcode regular expression matching那道题问个google老题的最佳解法
相关话题的讨论汇总
话题: ptr话题: states话题: 字符话题: old话题: p2