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)
网友评论