leetcode有很多國(guó)人用戶(hù)拆又，嘗試一個(gè)新的方式分享答案儒旬。
方便大家評(píng)論，提問(wèn)帖族，互動(dòng)义矛，打賞。
作為嘗試盟萨，是不是應(yīng)該選一個(gè)言簡(jiǎn)意賅的題目...
Sub Problem 0
首先做一點(diǎn)準(zhǔn)備工作凉翻。
target和stamp, 首尾字母必須一致。
不然target肯定是無(wú)法實(shí)現(xiàn)的捻激。
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每一個(gè)字符制轰，所在stamp中對(duì)應(yīng)的位置前计，并存在變量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]
如果我們能找到這樣一個(gè)滿(mǎn)足要求的path垃杖，那么表示target是可以實(shí)現(xiàn)的男杈。
首先觀察一下target，看看有什么規(guī)律调俘。假設(shè)有相鄰的兩個(gè)字母ab伶棒，必定符合以下的規(guī)律中的一個(gè)：
rule 0: ab 是 stamp中兩個(gè)連續(xù)的字母
rule 1: a是stamp的最后一個(gè)字母，b是stamp任意一個(gè)字母彩库。
rule 2: b是stamp的第一個(gè)字母肤无，a是stamp任意一個(gè)字母。
相鄰兩個(gè)字符骇钦，是有規(guī)律可循的宛渐，由此我們想到用DFS，結(jié)合以上三條規(guī)律來(lái)構(gòu)造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
根據(jù)path, 來(lái)復(fù)原操作窥翩。
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]
當(dāng)path里的數(shù)字不連續(xù)的時(shí)候，對(duì)應(yīng)rule 2或者rule 3鳞仙。
這是說(shuō)明出現(xiàn)了另一個(gè)stamp寇蚊，我們跳躍到了另一個(gè)stamp的index上。
rule 1
a是stamp的最后一個(gè)字母棍好，b是stamp任意一個(gè)字母仗岸。
新出現(xiàn)郵票是貼在上面，
我們把它的位置i,
加入列表up中梳玫。
rule 2
b是stamp的第一個(gè)字母，a是stamp任意一個(gè)字母右犹。
新出現(xiàn)郵票是被壓在下面的提澎，我們把它的位置i - path[i]，
加入列表down中念链。
最后盼忌，down中的郵票，我們倒序貼掂墓。up的中的郵票谦纱，正序貼，就可以構(gòu)造出對(duì)應(yīng)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)
