求助一个 G 家高频题的最优解

lokilokiloki 发表于 2019-5-4 01:03
我不觉得这个是Travelling Salesman Problem, 因为 TSP 要求每个点都要经过但是这个题只要求找前后词 mat ...

LC原题是TSP，因为要求用上所有的词，几遍没有overlap.比如abc和de仍然需要返回abcde

补充内容 (2019-5-4 07:23):
即便*

wisdompeak2 发表于 2019-5-3 08:15
既然题目给出的是list，那么我默认这些词是有顺序的。
如果是这样的话，那显然就是DP啊，而且就是个medium ...

能具体说一下是哪些词有顺序嘛？

目测当成求 shortest path 一样，先用 n**2 时间 求每个词之间的距离，在这里则是词语重叠的长度，然后用bfs + 优先队列找最远距离。时间复杂度 O(n**2)