给定一个字符串数组 A,找到以 A
中每个字符串作为子字符串的最短字符串。
我们可以假设 A
中没有字符串是 A
中另一个字符串的子字符串。
1.1 <= A.length <= 12
2.1 <= A[i].length <= 20
样例 1:
输入:["alex","loves","lintcode"]
输出:"alexloveslintcode"
解释:"alex","loves","lintcode"的全排列可以作为答案
样例 2:
输入:["catg","ctaagt","gcta","ttca","atgcatc"]
输出:"gctaagttcatgcatc"
解释:"gctaagttcatgcatc"中包含在A中的子串是"gcta","ctaagt","ttca","catg","atgcatc"。
在线评测地址: lintcode题解
【题解】
考点:dp
题解:1.我们必须把单词放在一行中,每个单词都可能与前一个单词重叠。尽量使单词的总重叠量最大化。
2.假设我们已经把一些单词放在我们的行中,以单词A[i]结尾。现在假设我们把单词A[j]作为下一个单词,而单词A[j]还没有被放下。重叠量增加A[i]和A[j]重叠部分。
3.我们可以使用动态规划来解决。让dp(mask,i)表示放下一些单词(由mask表示放下哪些单词)后的总重叠量,其中A[i]是最后一个放下的单词。然后,关键是dp(mask ^(1<<j),j)=max(overlap(a[i],a[j])+dp(mask,i))。
4.当然,这只告诉我们每一组单词的最大重叠是什么。我们还需要记住沿途的每一个选择(即使dp(mask ^(1<<j),j)达到最小值的具体i),这样就可以重建答案。
class Solution {
public String shortestSuperstring(String[] A) {
int N = A.length;
// Populate overlaps
int[][] overlaps = new int[N][N];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) if (i != j) {
int m = Math.min(A[i].length(), A[j].length());
for (int k = m; k >= 0; --k)
if (A[i].endsWith(A[j].substring(0, k))) {
overlaps[i][j] = k;
break;
}
}
}
// dp[mask][i] = most overlap with mask, ending with ith element
int[][] dp = new int[1<<N][N];
int[][] parent = new int[1<<N][N];
for (int mask = 0; mask < (1<<N); ++mask) {
Arrays.fill(parent[mask], -1);
for (int bit = 0; bit < N; ++bit) {
if (((mask >> bit) & 1) > 0) {
// Let's try to find dp[mask][bit]. Previously, we had
// a collection of items represented by pmask.
int pmask = mask ^ (1 << bit);
if (pmask == 0) {
continue;
}
for (int i = 0; i < N; ++i) if (((pmask >> i) & 1) > 0) {
// For each bit i in pmask, calculate the value
// if we ended with word i, then added word 'bit'.
int val = dp[pmask][i] + overlaps[i][bit];
if (val > dp[mask][bit]) {
dp[mask][bit] = val;
parent[mask][bit] = i;
}
}
}
}
}
// # Answer will have length sum(len(A[i]) for i) - max(dp[-1])
// Reconstruct answer, first as a sequence 'perm' representing
// the indices of each word from left to right.
int[] perm = new int[N];
boolean[] seen = new boolean[N];
int t = 0;
int mask = (1 << N) - 1;
// p: the last element of perm (last word written left to right)
int p = 0;
for (int j = 0; j < N; ++j) {
if (dp[(1<<N) - 1][j] > dp[(1<<N) - 1][p]) {
p = j;
}
}
// Follow parents down backwards path that retains maximum overlap
while (p != -1) {
perm[t++] = p;
seen[p] = true;
int p2 = parent[mask][p];
mask ^= 1 << p;
p = p2;
}
// Reverse perm
for (int i = 0; i < t/2; ++i) {
int v = perm[i];
perm[i] = perm[t-1-i];
perm[t-1-i] = v;
}
// Fill in remaining words not yet added
for (int i = 0; i < N; ++i) if (!seen[i])
perm[t++] = i;
// Reconstruct final answer given perm
StringBuilder ans = new StringBuilder(A[perm[0]]);
for (int i = 1; i < N; ++i) {
int overlap = overlaps[perm[i-1]][perm[i]];
ans.append(A[perm[i]].substring(overlap));
}
return ans.toString()
更多语言代码参见:leetcode/lintcode题解
网友评论