The problem of finding the shortest common superstring of a set of strings is a classic problem in string manipulation and can be solved using dynamic programming. The basic idea is to use a table to store the lengths of the shortest common superstrings of all possible combinations of substrings from the set of input strings. We then can reconstruct the shortest common superstring by backtracking through the table.
Here’s how to implement the solution using dynamic programming:
1. Build a graph whose vertices are the strings and the edges are the overlaps of the strings. An overlap occurs when the end of one string matches the beginning of another string.
2. Find the shortest path that visits every vertex exactly once. This is equivalent to finding the Hamiltonian path in the graph.
3. Once we have the shortest path, we can concatenate the strings in the order they appear on the path, skipping over the overlapping characters of adjacent strings.
4. If an overlapping character is found, we just keep the non-overlapping part.
5. Return the resulting superstring.
For example, let’s say we are given the input strings "ACGT", "CGTA", "GTAC", "TACG". We can build a graph with vertices "ACGT", "CGTA", "GTAC", "TACG" and edges between each pair of vertices that overlap.
ACGT CGTA GTAC TACG
| | | |
CGTA GTAC ACGT ACGT
| | | |
GTAC TACG CGTA CGTA
| | | |
TACG ACGT TACG GTACWe can then use dynamic programming to solve this problem by creating a table of size 24x4 for all the possible combinations of the vertices and their lengths.
ACGT CGTA GTAC TACG
0000 0 0 0 0
0001 4 4 4 4
0010 4 4 4 4
0011 7 6 7 6
0100 4 4 4 4
0101 7 7 7 7
0110 7 7 7 7
0111 10 9 10 9
1000 4 4 4 4
1001 7 7 7 7
1010 7 7 7 7
1011 10 10 10 10
1100 7 7 7 7
1101 10 10 10 10
1110 10 10 10 10
1111 13 12 13 12The cell at the bottom-right corner of the table shows the length of the shortest common superstring for all the input strings. We can then backtrack through the table to find the actual superstring by following the path with the shortest length. Using the same example, the optimal order of concatenating the strings together is "ACGTACGTA" which is the shortest common superstring for the given set of input strings.
Here’s the Java code for the solution:
public static String shortestCommonSuperstring(String[] strings) {
int n = strings.length;
int[][] dp = new int[1 << n][n];
int[][] overlaps = new int[n][n];
// Create overlaps graph
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
int p = 0;
while (p < strings[i].length() && strings[j].startsWith(strings[i].substring(p))) {
p++;
}
overlaps[i][j] = p;
}
}
}
// Populate dp table
for (int i = 1; i < (1 << n); i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) > 0) {
if (i == 1 << j) {
dp[i][j] = strings[j].length();
} else {
for (int k = 0; k < n; k++) {
if (k != j && (i & (1 << k)) > 0 && dp[i - (1 << j)][k] != Integer.MAX_VALUE) {
dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + strings[j].length() - overlaps[k][j]);
}
}
}
}
}
}
// Trace back shortest path to reconstruct superstring
int minIndex = 0, minVal = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (dp[(1 << n) - 1][i] < minVal) {
minIndex = i;
minVal = dp[(1 << n) - 1][i];
}
}
StringBuilder sb = new StringBuilder(strings[minIndex]);
int used = 1 << minIndex;
while (used < (1 << n)) {
int next = -1;
for (int i = 0; i < n; i++) {
if ((used & (1 << i)) == 0 && dp[used][minIndex] == dp[used | (1 << i)][i] + strings[i].length() - overlaps[minIndex][i]) {
next = i;
break;
}
}
sb.append(strings[next].substring(overlaps[minIndex][next]));
used |= 1 << next;
minIndex = next;
}
return sb.toString();
}