leetcode-44. Wildcard Matching

leanxi 发布于2019-07-30 17:20 / 1472人阅读

摘要：正则由于的存在，所以有多种状态，中间状态储存都需要记录下来。然后以这些状态为动态的中转，继续判断到最后。最后正则匹配字符串是否成功的判断依据，就是正则字符串的最大，是否出现在遍历到最后的状态列表中。

题目阐释：

正则匹配字符串，用程序实现

关键理解：

正则匹配，动态规划思想，一个个向后追溯，后面的依赖前面的匹配成功。
正则和待匹配的字符串长度不一，统一到正则字符串的index索引上，每次的字符串index移动，都以匹配到的正则的index为准。
正则由于*?的存在，所以有多种状态，中间状态储存都需要记录下来。然后以这些状态为动态的中转，继续判断到最后。
最后正则匹配字符串是否成功的判断依据，就是正则字符串的最大index，是否出现在遍历到最后的状态列表中。

错误之处：

多处动态变化，导致无法入手，*没有处理思路，没有找到匹配成功的条件

应用：

正则属于多条路径问题，可以推理到 多种渠道的问题，匹配成功当前的才往后推
*相当于无限向后匹配，所以无限循环使用，看能否匹配成功。

Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for "?" and "*".

"?" Matches any single character.
"*" Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:

s = "aa"
p = "a"

Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:

s = "aa"
p = "*"

Output: true
Explanation: "*" matches any sequence.

Example 3:

Input:

s = "cb"
p = "?a"

Output: false
Explanation: "?" matches "c", but the second letter is "a", which does not match "b".

Example 4:

Input:

s = "adceb"
p = "*a*b"

Output: true
Explanation: The first "" matches the empty sequence, while the second "" matches the substring "dce".

Example 5:

Input:

s = "acdcb"
p = "a*c?b"

Output: false

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        transfer = {}
        index=0
        for char in p:
            if char=="*":
                transfer[index,char]=index
            else:
                transfer[index,char]=index+1
                index+=1
        accept=index

        # index=0
        state = {0}
        for char in s:
            state_tmp=set()
            for index in state:
                for char_prob in [char,"?","*"]:
                    index_next=transfer.get((index,char_prob))
                    state_tmp.add(index_next)
            state=state_tmp
        return accept in state


if __name__=="__main__":
    s = "acdcb"
    p = "a*c?b"
    p = "a**c?d"
    st=Solution()
    out=st.isMatch(s,p)
    print(out)

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42165.html

Leetcode 44 Wildcard Matching 通配符匹配

摘要：难度题目给出一个字符串和一个要求我们给出这个字符串是否匹配这个其中通配符跟我们平常见到的一样是和代表任意单个字符代表一个或多个字符这个题跟简单正则匹配比较类似可以跟这里面第二个解法一样采取类似的动态规划解法在里取中间某个确定的字符串序列将字 Implement wildcard pattern matching with support for ? and *. ? Matches ...

SimonMa 2019-08-14 17:16 评论0 收藏0
[Leetcode] Wildcard Matching 通配符匹配

摘要：当我们遇到一个时，因为之后可能要退回至该位置重新匹配，我们要将它的下标记录下来，比如。但是，当我们连续遇到两次的情况，如何保证我还是能继续匹配，而不是每次都退回导致循环呢所以我们还要记录一个，用来记录用上一个连续匹配到的中的下标。 Wildcard Matching Implement wildcard pattern matching with support for ? and ...

tainzhi 2019-08-14 12:35 评论0 收藏0
[LintCode/LeetCode] Wildcard Matching

摘要：递归和动规的方法没有研究，说一下较为直观的贪心算法。用和两个指针分别标记和进行比较的位置，当遍历完后，若也遍历完，说明完全配对。当之前出现过，且此时和完全无法配对的时候，就一起退回在和配对过的位置。再将和逐个加继续比较，并将后移。 Problem Implement wildcard pattern matching with support for ? and *. ? Matche...

Ethan815 2019-08-14 15:43 评论0 收藏0
Wildcard Matching

摘要：题目链接这道题还是可以用的方法，用的数组来解，空间复杂度较高。和不同，这道题的符号和前面的没有关系，不需要一起考虑。最坏的情况下，间隔出现且每个都要匹配很多字符，设一个平均匹配里面个字符，。其中，是的长度，是的长度。 Wildcard Matching 题目链接：https://leetcode.com/problems...这道题还是可以用Regular Expression Mat...

galaxy_robot 2019-08-14 17:19 评论0 收藏0
LC44 wildcard matching

摘要：各一个指针，表示上一次真正到的位置。在的时候，上，增加下一步知道出界，发现是错误的所以需要回到上次的地方，即一旦走出去，无法返回，需要一个指针记录最后的地方。 public class Solution { public boolean isMatch(String s, String p) { int idxs = 0, idxp = 0, idxmatch ...

Tychio 2019-08-14 17:17 评论0 收藏0