"ABBBBBBG"
["BDD","BFB","FDA","CCC","FBD","FBG","EEB","GBA","CFB","ECB","GDA","ECC","EFE","FCA","DBA","FAD","BEE","GEC","CFC","CFD","BCG","CAC","FCC","GAC","CAG","CFF","BEC","EAD","GBE","FEG","BDC","GBF","FBB","FBE","DDG","FDF","EDF","FAF","BEB","DDE","EEA","FAG","GDC","DFE","CDB","DFD","GDD","DAF","ECE","DBG","DDD","EFG","FAC","FEC","GED","DEE","CCF","EFD","FDE","GDF","ECG","DAE","FCG","DCA","EAF","EED","EEE","FEA","BFG","EAA","GDE","CEB","FAE","BDE","EBB","GFD","DBB","BFD","EFF","DAD","CDC","DCD","FFD","DBD","EFA","BCB","ECF","CFA","GFF","CFG","EEG","DAG","CAE","FED","CCA","EDE","FDG","BEF","FDD","BEG","FFE","DDC","BCE","GAA","GFE","FFF","CFE","BDF","DFG","DEF","FEF","GEE","EAB","GDB","CEE","BDA","DEG","DEC","GCG","DFB","EFB","GAB","CDF","CAF","BAB","GCC","DDA","CDD","FCB","DAA","GBG","BAC","GCE","GAG","EAE","EBG","GBD","BFE","CCD","EDD","FCD","FBC","DEB","EDG","GEA","EBE","GDG","DBE","BCD","GBB","FEB","DED","CAD","EDB","CED","GCD","BFC","GAE","CEG","EEC","FEE","GCA","FCF","ECD","DCC","BDB","EBD","DCE","BAE","FFG","DDF","DCF","BED","CAA","BCF","GBC","CCB","BCC","GFC","FFB","DFA","BBA","BBB","BBC","BBD","BBE","BBF","BBG","AAA","ABA","ACA","ADA","AEA","AFA","BGG","CGG","DGG","EGG","FGG","GGG"]
回溯法能过的唯一原因是数据太弱。
上面的测试用例的构造思路是这样的:形如A*的如AA,AB,AC...,但除AG以外,都只能放A,形如*G如BG,CG,...,但除AG以外,都只能放G。AG上没有能放的字母。其他组合上面能放几乎所有字母。
可以看出来对这个例子来说,每一层最左边只能是A,最右边只能是G,倒数第二层只能是AG,而AG上不能放字母,因此无解。但是所有的解都是在最后一步才失败的,因此遍历过的状态数极其巨大。
以官方题解为例,官方题解主要包括朴素的回溯和按行去重两种方法。朴素回溯的复杂度是O(A^(N^2)),而非题解说的O(A^N),对于这个测试例来说,无论C++还是Java都会炸,Python就更不用说了。
按行去重也就是官方Java题解中用的方法,遇到整行的时候会缓存整行的结果,这可以将复杂度降至O(A^(2N)),差的这一点可以让Java通过(Java用位运算hash的方式常数也比较低),但是官方题解的Python即使打开seen的hash也会炸。
能通过的方法是将中途所有的状态都保存下来去重。每次尝试在下一层两个字母上堆一个字母的时候,下一层有一个字母就被压到底部了,它与后续求解无关,因此当前状态永远可以用上一层已经堆上的字母 + 下一层仍然露出来的字母来表示,总的状态数是O(NA^N),正好在可以通过的范围内。
###python3
from functools import lru_cache
class Solution:
def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
trans = {}
for p in allowed:
trans.setdefault(p[:2], []).append(p[2])
@lru_cache(None)
def search(a, b):
if len(a) == 2:
if not b:
return a in trans
else:
return any(search(b + t, '') for t in trans.get(a, []))
else:
return any(search(a[1:], b + t) for t in trans.get(a[:2], []))
return search(bottom, '')
事实上这并不是最强的测试例,以下测试例耗时会更长:
"ADDDDDDA"
["ADA","ADB","ADC","AEA","AEB","AEC","AFA","AFB","AFC","AGA","AGB","AGC","BDA","BDB","BDC","BEA","BEB","BEC","BFA","BFB","BFC","BGA","BGB","BGC","CDA","CDB","CDC","CEA","CEB","CEC","CFA","CFB","CFC","CGA","CGB","CGC","DAA","DAB","DAC","DBA","DBB","DBC","DCA","DCB","DCC","EAA","EAB","EAC","EBA","EBB","EBC","ECA","ECB","ECC","FAA","FAB","FAC","FBA","FBB","FBC","FCA","FCB","FCC","GAA","GAB","GAC","GBA","GBB","GBC","GCA","GCB","GCC","DDA","DDB","DDC","DEA","DEB","DEC","DFA","DFB","DFC","DGA","DGB","DGC","EDA","EDB","EDC","EEA","EEB","EEC","EFA","EFB","EFC","EGA","EGB","EGC","FDA","FDB","FDC","FEA","FEB","FEC","FFA","FFB","FFC","FGA","FGB","FGC","GDA","GDB","GDC","GEA","GEB","GEC","GFA","GFB","GFC","GGA","GGB","GGC","DDD","DDE","DDF","DDG","DED","DEE","DEF","DEG","DFD","DFE","DFF","DFG","DGD","DGE","DGF","DGG","EDD","EDE","EDF","EDG","EED","EEE","EEF","EEG","EFD","EFE","EFF","EFG","EGD","EGE","EGF","EGG","FDD","FDE","FDF","FDG","FED","FEE","FEF","FEG","FFD","FFE","FFF","FFG","FGD","FGE","FGF","FGG","GDD","GDE","GDF","GDG","GED","GEE","GEF","GEG","GFD","GFE","GFF","GFG","GGD","GGE","GGF","GGG"]
"ADDDDDDA"
["GDF","EFB","FFC","DCB","GFD","GCD","BGA","EEC","DEC","EDD","CDA","FEF","CGD","ECA","DGD","FFD","BEA","GEE","EDE","CED","GEF","BCA","CFB","GGA","GGB","FDE","FGE","GAB","FBA","FFA","ECF","FDA","CCD","CGA","DED","EBB","FFG","BFB","FCB","DGE","DDB","BEB","GDG","FDB","FFB","CGB","GFE","FEG","FDC","CDF","GCE","DFD","DFG","CCA","GFA","FCE","BDA","ACA","CDB","GDE","EEA","FBB","FEC","DCA","FAB","CCE","GGF","CAA","EEF","CDD","FGA","DDC","CGC","DFF","CEE","EDC","FCA","GBB","CEC","DEE","DEB","AFB","EEG","FGB","FCD","GFC","GCA","DDD","FGC","ECC","FDF","GEC","DBB","DFB","EED","GAA","FGD","DBA","DCD","EBA","FCF","ECG","CDE","DCE","EAA","DAB","FDD","DFC","GGD","BGB","CBA","GDC","AGB","BFA","EFD","EGA","FAA","GEG","EAB","EDA","DEA","CEA","DCC","GCG","DAA","ECD","GFB","GBA","GCF","EEE","AFA","EGC","AGA","FEB","CCF","DGA","FFF","CCB","DDA","BCB","ADA","ECB","DGG","EGE","CFC","GCC","FGF","FDG","CGF","DDE","AEB","GGG","CCC","DCG","DDG","CEF","FGG","ACB","DFE","BDB","CCG","CGG","CFG","DGC","EFC","GDB","FEE","EDB","CFF","EFF","FEA","EFE","GEA","CDC","EDF","CGE","CFA","GGC","DEG","FCC","FFE","CFD","EDG","CAB","CEB","GDA","EGB","ECE","GCB","DGF","DGB","EGF","EGG","CEG","GFG","ADB","EFA","GFF","DEF","GEB"]
"AGGGGGGA"
["AFA","AFB","AFC","AFD","AFE","AGA","AGB","AGC","AGD","AGE","BFA","BFB","BFC","BFD","BFE","BGA","BGB","BGC","BGD","BGE","CFA","CFB","CFC","CFD","CFE","CGA","CGB","CGC","CGD","CGE","DFA","DFB","DFC","DFD","DFE","DGA","DGB","DGC","DGD","DGE","EFA","EFB","EFC","EFD","EFE","EGA","EGB","EGC","EGD","EGE","FAA","FAB","FAC","FAD","FAE","FBA","FBB","FBC","FBD","FBE","FCA","FCB","FCC","FCD","FCE","FDA","FDB","FDC","FDD","FDE","FEA","FEB","FEC","FED","FEE","GAA","GAB","GAC","GAD","GAE","GBA","GBB","GBC","GBD","GBE","GCA","GCB","GCC","GCD","GCE","GDA","GDB","GDC","GDD","GDE","GEA","GEB","GEC","GED","GEE","FFA","FFB","FFC","FFD","FFE","FGA","FGB","FGC","FGD","FGE","GFA","GFB","GFC","GFD","GFE","GGA","GGB","GGC","GGD","GGE","FFF","FFG","FGF","FGG","GFF","GFG","GGF","GGG"]
这两个测试例的构造思路是,将字母分成两类,一类是Type-0,一类是Type-1。0和0上不能放数字,0和1、1和0上只能放0类数字,而1和1上能放全部数字。然后给出的串两侧是Type-0字母,中间全部是Type-1字母。区别在于第一个使用ABC作为Type-0,第二个使用ABCD,第三个使用ABCDE。别看ABCDE时的allow数组似乎最短,但它对前面的算法威胁是最大的,因为最前面的测试例每一行两侧的字母固定是A和G,而这个例子中两侧的字母可以选择的数量更多,每一行中中间可以使用所有字母,两侧只能用Type-0,因此最后一个测试例的状态数是文章最开始测试例状态数的25倍。
这三个测试例可以炸掉LeetCode的标程,让标程超时(标程大概就是官方题解中记忆化的Java版本)。最后一个测试例可以炸掉上面的Python答案(如果改用Java或C++估计可以通过)。
在前面答案的基础上进行提前剪枝,可以减少状态数,通过这几个测试例:
###python3
from functools import lru_cache
class Solution:
def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
trans = {}
for p in allowed:
trans.setdefault(p[:2], []).append(p[2])
@lru_cache(None)
def search(a, b):
if len(b) >= 2:
if not search(b, ''):
return False
if len(a) == 2:
if not b:
return a in trans
else:
return any(search(b + t, '') for t in trans.get(a, []))
else:
return any(search(a[1:], b + t) for t in trans.get(a[:2], []))
return search(bottom, '')
注意到在处理(a,b)时,提前判断了(b,'')是否可行。这个判断对题目最开始的测试例没有太大帮助,但对后面这几个测试例有一定作用,主要是有效防止枚举出Type-0字符。目前没有已知的测试例可以fail这个程序了。