Find the Shortest Superstring LeetCode solution in JavaScript

1
var shortestSuperstring = function (words) {
2
  let N = words.length,
3
    suffixes = new Map(),
4
    edges = Array.from({ length: N }, () => new Uint8Array(N));
5

6
  // Build the edge graph
7
  for (let i = 0, word = words; i < N; i++) {
8
    let word = words[i];
9
    for (let k = 1; k < word.length; k++) {
10
      let sub = word.slice(k);
11
      if (suffixes.has(sub)) suffixes.get(sub).push(i);
12
      else suffixes.set(sub, [i]);
13
    }
14
  }
15
  for (let j = 0; j < N; j++) {
16
    let word = words[j];
17
    for (let k = 1; k < word.length; k++) {
18
      let sub = word.slice(0, k);
19
      if (suffixes.has(sub))
20
        for (let i of suffixes.get(sub)) edges[i][j] = Math.max(edges[i][j], k);
21
    }
22
  }
23

24
  // Initialize DP array
25
  let M = N - 1,
26
    dp = Array.from({ length: M }, () => new Uint16Array(1 << M));
27

28
  // Helper function to find the best value for dp[curr][currSet]
29
  // Store the previous node with bit manipulation for backtracking
30
  const solve = (curr, currSet) => {
31
    let prevSet = currSet - (1 << curr),
32
      bestOverlap = 0,
33
      bestPrev;
34
    if (!prevSet) return (edges[M][curr] << 4) + M;
35
    for (let prev = 0; prev < M; prev++)
36
      if (prevSet & (1 << prev)) {
37
        let overlap = edges[prev][curr] + (dp[prev][prevSet] >> 4);
38
        if (overlap >= bestOverlap) (bestOverlap = overlap), (bestPrev = prev);
39
      }
40
    return (bestOverlap << 4) + bestPrev;
41
  };
42

43
  // Build DP using solve
44
  for (let currSet = 1; currSet < 1 << M; currSet++)
45
    for (let curr = 0; curr < N; curr++)
46
      if (currSet & (1 << curr)) dp[curr][currSet] = solve(curr, currSet);
47

48
  // Join the ends at index M
49
  let curr = solve(M, (1 << N) - 1) & ((1 << 4) - 1);
50

51
  // Build the circle by backtracking path info from dp
52
  // and find the best place to cut the circle
53
  let path = [curr],
54
    currSet = (1 << M) - 1,
55
    bestStart = 0,
56
    lowOverlap = edges[curr][M],
57
    prev;
58
  while (curr !== M) {
59
    (prev = dp[curr][currSet] & ((1 << 4) - 1)), (currSet -= 1 << curr);
60
    let overlap = edges[prev][curr];
61
    if (overlap < lowOverlap)
62
      (lowOverlap = overlap), (bestStart = N - path.length);
63
    (curr = prev), path.unshift(curr);
64
  }
65

66
  // Build and return ans by cutting the circle at bestStart
67
  let ans = [];
68
  for (let i = bestStart; i < bestStart + M; i++) {
69
    let curr = path[i % N],
70
      next = path[(i + 1) % N],
71
      word = words[curr];
72
    ans.push(word.slice(0, word.length - edges[curr][next]));
73
  }
74
  ans.push(words[path[(bestStart + M) % N]]);
75
  return ans.join("");
76
};