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)

最后编辑于：2018.11.04 11:00:59