难度: Hard
原题连接
内容描述
Given an array A of strings, find any smallest string that contains each string in A as a substring.
We may assume that no string in A is substring of another string in A.
Example 1:
Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.
Example 2:
Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"
Note:
1 <= A.length <= 12
1 <= A[i].length <= 20
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
贪心，但是我觉得是test case太少了，下面这个解法应该是错的, 事实证明确实是错的
input: ["abcd", "cde", "dfcd"]
Running the above code yields 'abcdedfcd' of length 9. The best solution should be 'abcfcde' of length 8.
The reason is the below dfs implementation greedily select the next word whenever some length reduction is available.
This may not always be the optimal strategy in some cases as shown by the counter example.
import itertools as it
class Solution:
def shortestSuperstring(self, A):
"""
:type A: List[str]
:rtype: str
"""
# return the max overlap length between two string, and the merge result of them
def findOverlappingPair(s1, s2):
max_overlap_len = -sys.maxsize
n = min(len(s1), len(s2))
res = ''
for i in range(1, n+1):
if s1.endswith(s2[:i]):
if max_overlap_len < i:
max_overlap_len = i
res = s1 + s2[i:]
for i in range(1, n+1):
if s2.endswith(s1[:i]):
if max_overlap_len < i:
max_overlap_len = i
res = s2 + s1[i:]
return max_overlap_len, res
n = len(A)
while n != 1:
p, q = -1, -1
res = ''
max_val = -sys.maxsize
for i in range(n):
for j in range(i+1, n):
r, tmp_res = findOverlappingPair(A[i], A[j])
if max_val < r:
max_val = r
res = tmp_res
p = j
q = i
n -= 1
if max_val == -sys.maxsize:
A[0] = A[0] + A[n]
else:
A[p] = res
A[q] = A[n]
return A[0]
思路 2 - 时间复杂度: O(N^2 * 2^N)- 空间复杂度: O(N * 2^N)******
beats 24.66%, 参考Clean python DP with explanations
class Solution:
def shortestSuperstring(self, A):
"""
:type A: List[str]
:rtype: str
"""
# construct a directed graph
# node i => A[i]
# weights are represented as an adjacency matrix:
# shared[i][j] => length saved by merging A[i] and A[j] in the way of A[i][:-k] + A[i][-k:] + A[j][k:]
n = len(A)
shared = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(min(len(A[i]), len(A[j])), -1, -1):
if A[i][-k:] == A[j][:k]:
shared[i][j] = k
break
# The problem becomes finding the shortest path that visits all nodes exactly once.
# Brute force DFS would take O(n!) time.
# A DP solution costs O(n^2 * 2^n) time.
#
# Let's consider integer from 0 to 2^n - 1.
# Each i contains 0-n 1 bits. Hence each i selects a unique set of strings in A.
# Let's denote set(i) => {A[j] | j-th bit of i is 1}
# dp[i][k] => shortest superstring of set(i) ending with A[k]
#
# e.g.
# if i = 5 i.e. 110 in binary. dp[5][k] considers superstring of A[2] and A[1].
# dp[5][1] => the shortest superstring of {A[2], A[1]} ending with A[1].
# For this simple case dp[5][1] = concatenate(A[2], A[1])
dp = [[''] * n for _ in range(1 << n)]
for i in range(1 << n):
for k in range(n):
if not (i & (1 << k)): # skip if A[k] is not in set(i)
continue
if i == 1 << k: # if set(i) == {A[k]}, no merge happens
dp[i][k] = A[k]
continue
for j in range(n):
if j == k:
continue
if i & (1 << j):
# the shortest superstring if we remove A[k] from the set(i)
s = dp[i ^ (1 << k)][j]
# don't forget to add the rest part of merging result between A[j] and A[k]
s += A[k][shared[j][k]:]
# if this is the first time we handle dp[i][k] or current res is shorter
if dp[i][k] == '' or len(s) < len(dp[i][k]):
dp[i][k] = s
min_len = float('inf')
res = ''
# find the shortest superstring of all candidates ending with different string
for i in range(n):
s = dp[(1 << n) - 1][i]
if len(s) < min_len:
min_len, res = len(s), s
return res