Last active
May 23, 2021 18:38
-
-
Save xiaq/3e0fb8f3cd49027a215f4856af68f3e9 to your computer and use it in GitHub Desktop.
LeetCode 943 "Find the Shortest Superstring", Java version
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
String[] words; | |
int n; | |
int[][] prefix; // prefix[i][j] is the minimal k such that words[i][k:] is a prefix of words[j] | |
int[][] answer; // answer[first][ban] | |
public String shortestSuperstring(String[] words) { | |
init(words); | |
int first = -1; | |
int min = Integer.MAX_VALUE; | |
for (int i = 0; i < n; i++) { | |
int v = search(i, 0); | |
if (min > v) { | |
min = v; | |
first = i; | |
} | |
} | |
int[] seq = reconstruct(first); | |
StringBuilder s = new StringBuilder(); | |
for (int i = 0; i < n; i++) { | |
if (i == n-1) { | |
s.append(words[seq[i]]); | |
} else { | |
s.append(words[seq[i]].substring(0, prefix[seq[i]][seq[i+1]])); | |
} | |
} | |
return s.toString(); | |
} | |
void init(String[] s) { | |
words = s; | |
n = words.length; | |
prefix = new int[n][n]; | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < n; j++) { | |
if (i == j) { | |
continue; | |
} | |
for (int k = 0; k <= words[i].length(); k++) { | |
if (words[j].startsWith(words[i].substring(k))) { | |
prefix[i][j] = k; | |
break; | |
} | |
} | |
} | |
} | |
answer = new int[n][1 << n]; | |
} | |
// Ban set manipulation | |
static boolean has(int ban, int i) { return (ban & (1 << i)) != 0; } | |
static int with(int ban, int i) { return ban | (1 << i); } | |
int search(int first, int ban) { | |
if (answer[first][ban] != 0) { | |
return answer[first][ban]; | |
} | |
int newban = with(ban, first); // Ban the first now that we're using it | |
if (newban == (1 << n) - 1) { | |
// No other words to use | |
int v = words[first].length(); | |
answer[first][ban] = v; | |
return v; | |
} | |
int min = Integer.MAX_VALUE; | |
for (int i = 0; i < n; i++) { | |
if (has(newban, i)) { | |
continue; | |
} | |
int v = prefix[first][i] + search(i, newban); | |
min = Math.min(min, v); | |
} | |
answer[first][ban] = min; | |
return min; | |
} | |
int[] reconstruct(int first) { | |
int[] seq = new int[n]; | |
seq[0] = first; | |
int prev = first; | |
int prevban = 0; | |
for (int d = 1; d < n; d++) { | |
// The following mirrors the search method above | |
int ban = with(prevban, prev); | |
for (int i = 0; i < n; i++) { | |
if (has(ban, i)) { | |
continue; | |
} | |
if (answer[prev][prevban] == prefix[prev][i] + answer[i][ban]) { | |
seq[d] = i; | |
prev = i; | |
prevban = ban; | |
} | |
} | |
} | |
return seq; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment