美文网首页LeetCode
Leetcode 936 Stamping The Sequen

Leetcode 936 Stamping The Sequen

作者: lee_5a30 | 来源:发表于2018-11-04 10:59 被阅读1439次

    leetcode有很多国人用户,尝试一个新的方式分享答案。
    方便大家评论,提问,互动,打赏
    作为尝试,是不是应该选一个言简意赅的题目...

    Sub Problem 0

    首先做一点准备工作。
    target和stamp, 首尾字母必须一致。
    不然target肯定是无法实现的。

        def movesToStamp(self, s, t):
            if s[0] != t[0] or s[-1] != t[-1]: return []
            n, m = len(s), len(t)
    

    Sub Problem 1

    我们尝试找到target每一个字符,所在stamp中对应的位置,并存在变量path中。

    Example 1:
    Input: stamp = "abc", target = "ababc"
    path = [0,1,0,1,2]

    Example 2:
    Input: stamp = "aabcaca", target = "abca"
    path = [0,0,1,2,3,2,3]

    如果我们能找到这样一个满足要求的path,那么表示target是可以实现的。
    首先观察一下target,看看有什么规律。假设有相邻的两个字母ab,必定符合以下的规律中的一个:

    rule 0: ab 是 stamp中两个连续的字母
    rule 1: a是stamp的最后一个字母,b是stamp任意一个字母。
    rule 2: b是stamp的第一个字母,a是stamp任意一个字母。

    相邻两个字符,是有规律可循的,由此我们想到用DFS,结合以上三条规律来构造path

            path = [0] * m
            pos = collections.defaultdict(set)
            for i, c in enumerate(s): pos[c].add(i)
    
            def dfs(i, index):
                path[i] = index
                if i == m - 1: return index == n - 1
                nxt_index = set()
                if index == n - 1: # rule 2
                    nxt_index |= pos[t[i + 1]]
                if s[index + 1] == t[i + 1]: # rule 0
                    nxt_index.add(index + 1)
                if s[0] == t[i + 1]: # rule 1
                    nxt_index.add(0)
                return any(dfs(i + 1, j) for j in nxt_index)
    

    Sub Problem 2

    根据path, 来复原操作。

    Example 1:
    Input: stamp = "abc", target = "ababc"
    path = [0,1,0,1,2]
    Output: [2,0]

    Example 2:
    Input: stamp = "aabcaca", target = "abca"
    path = [0,0,1,2,3,2,3]
    Output: [3,0,1]

    当path里的数字不连续的时候,对应rule 2或者rule 3。
    这是说明出现了另一个stamp,我们跳跃到了另一个stamp的index上。

    rule 1
    a是stamp的最后一个字母,b是stamp任意一个字母。
    新出现邮票是贴在上面,
    我们把它的位置i,
    加入列表up中。

    rule 2
    b是stamp的第一个字母,a是stamp任意一个字母。
    新出现邮票是被压在下面的,我们把它的位置i - path[i]
    加入列表down中。

    最后,down中的邮票,我们倒序贴。up的中的邮票,正序贴,就可以构造出对应path了。

            def path2res(path):
                down, up = [], []
                for i in range(len(path)):
                    if path[i] == 0:
                        up.append(i)
                    elif i and path[i] - 1 != path[i - 1]:
                        down.append(i - path[i])
                return down[::-1] + up
    

    你要是喜欢,也可以挤成一行:

    [i - path[i] for i in range(1, m) if path[i - 1] + 1 != path[i] > 0][::-1] + [i for i in range(m) if not path[i]]
    

    最后贴一下完整解答:

        def movesToStamp(self, s, t):
            if s[0] != t[0] or s[-1] != t[-1]: return []
            n, m = len(s), len(t)
            path = [0] * m
            pos = collections.defaultdict(set)
            for i, c in enumerate(s): pos[c].add(i)
    
            def dfs(i, index):
                path[i] = index
                if i == m - 1: return index == n - 1
                nxt_index = set()
                if index == n - 1:  # rule 2
                    nxt_index |= pos[t[i + 1]]
                if s[index + 1] == t[i + 1]:  # rule 0
                    nxt_index.add(index + 1)
                if s[0] == t[i + 1]:  # rule 1
                    nxt_index.add(0)
                return any(dfs(i + 1, j) for j in nxt_index)
    
            def path2res(path):
                down, up = [], []
                for i in range(len(path)):
                    if path[i] == 0:
                        up.append(i)
                    elif i and path[i] - 1 != path[i - 1]:
                        down.append(i - path[i])
                return down[::-1] + up
    
            if not dfs(0, 0): return []
            return path2res(path)
    

    相关文章

      网友评论

        本文标题:Leetcode 936 Stamping The Sequen

        本文链接:https://www.haomeiwen.com/subject/dpfrxqtx.html