Skip to content

943. Find the Shortest Superstring 👍

Approach 1: DFS

  • Time: $O(n!)$
  • Space: $O(n!)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
 public:
  string shortestSuperstring(vector<string>& words) {
    const int n = words.size();
    // cost[i][j] := the cost to append words[j] after words[i]
    vector<vector<int>> cost(n, vector<int>(n));

    // Returns the cost to append b after a.
    auto getCost = [](const string& a, const string& b) {
      int cost = b.length();
      const int minLength = min(a.length(), b.length());
      for (int k = 1; k <= minLength; ++k)
        if (a.substr(a.length() - k) == b.substr(0, k))
          cost = b.length() - k;
      return cost;
    };

    // Pre-calculate cost array to save time.
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        cost[i][j] = getCost(words[i], words[j]);
        cost[j][i] = getCost(words[j], words[i]);
      }

    vector<int> bestPath;
    int minLength = n * 20;  // given by problem

    dfs(words, cost, {}, bestPath, 0, 0, 0, minLength);

    string ans = words[bestPath[0]];

    for (int k = 1; k < n; ++k) {
      const int i = bestPath[k - 1];
      const int j = bestPath[k];
      ans += words[j].substr(words[j].length() - cost[i][j]);
    }

    return ans;
  }

 private:
  // used: i-th bit means words[i] is used or not
  void dfs(const vector<string>& words, const vector<vector<int>>& cost,
           vector<int>&& path, vector<int>& bestPath, int used, int depth,
           int currLength, int& minLength) {
    if (currLength >= minLength)
      return;
    if (depth == words.size()) {
      minLength = currLength;
      bestPath = path;
      return;
    }

    for (int i = 0; i < words.size(); ++i) {
      if (used >> i & 1)
        continue;
      path.push_back(i);
      const int newLength = depth == 0 ? words[i].length()
                                       : currLength + cost[path[depth - 1]][i];
      dfs(words, cost, std::move(path), bestPath, used | 1 << i, depth + 1,
          newLength, minLength);
      path.pop_back();
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
  public String shortestSuperstring(String[] words) {
    final int n = words.length;
    // cost[i][j] := the cost to append words[j] after words[i]
    int[][] cost = new int[n][n];

    // Pre-calculate cost array to save time.
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        cost[i][j] = getCost(words[i], words[j]);
        cost[j][i] = getCost(words[j], words[i]);
      }

    List<Integer> path = new ArrayList<>();
    List<Integer> bestPath = new ArrayList<>();

    minLength = n * 20; // given by problem

    dfs(words, cost, path, bestPath, 0, 0, 0);

    StringBuilder sb = new StringBuilder(words[bestPath.get(0)]);

    for (int k = 1; k < n; ++k) {
      final int i = bestPath.get(k - 1);
      final int j = bestPath.get(k);
      sb.append(words[j].substring(words[j].length() - cost[i][j]));
    }

    return sb.toString();
  }

  private int minLength;

  // Returns the cost to append b after a.
  private int getCost(final String a, final String b) {
    int cost = b.length();
    final int minLength = Math.min(a.length(), b.length());
    for (int k = 1; k <= minLength; ++k)
      if (a.substring(a.length() - k).equals(b.substring(0, k)))
        cost = b.length() - k;
    return cost;
  }

  // used: i-th bit means words[i] is used or not
  private void dfs(String[] words, int[][] cost, List<Integer> path, List<Integer> bestPath,
                   int used, int depth, int currLength) {
    if (currLength >= minLength)
      return;
    if (depth == words.length) {
      minLength = currLength;
      bestPath.clear();
      for (final int node : path) {
        bestPath.add(node);
      }
      return;
    }

    for (int i = 0; i < words.length; ++i) {
      if ((used >> i & 1) == 1)
        continue;
      path.add(i);
      final int newLength =
          depth == 0 ? words[i].length() : currLength + cost[path.get(depth - 1)][i];
      dfs(words, cost, path, bestPath, used | 1 << i, depth + 1, newLength);
      path.remove(path.size() - 1);
    }
  }
}

Approach 2: DP

  • Time: $O(n \cdot 2^n)$
  • Space: $O(n \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
 public:
  string shortestSuperstring(vector<string>& words) {
    const int n = words.size();
    // cost[i][j] := the cost to append words[j] after words[i]
    vector<vector<int>> cost(n, vector<int>(n));
    // dp[s][j] := the minimum cost to visit nodes of s ending in j, s is a
    // binary Value, e.g. dp[6][2] means the minimum cost to visit {1, 2} ending
    // in 2 (6 = 2^1 + 2^2)
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));
    // parent[s][j] := the parent of "nodes of s ending in j"
    vector<vector<int>> parent(1 << n, vector<int>(n, -1));

    // Returns the cost to append b after a.
    auto getCost = [](const string& a, const string& b) {
      int cost = b.length();
      const int minLength = min(a.length(), b.length());
      for (int k = 1; k <= minLength; ++k)
        if (a.substr(a.length() - k) == b.substr(0, k))
          cost = b.length() - k;
      return cost;
    };

    // Pre-calculate the `cost` array to save time.
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        cost[i][j] = getCost(words[i], words[j]);
        cost[j][i] = getCost(words[j], words[i]);
      }

    for (int i = 0; i < n; ++i)
      dp[1 << i][i] = words[i].length();

    // Enumerate all the states ending in different nodes.
    for (int s = 1; s < (1 << n); ++s)
      for (int i = 0; i < n; ++i) {
        if ((s & (1 << i)) == 0)
          continue;
        for (int j = 0; j < n; ++j)
          if (dp[s - (1 << i)][j] + cost[j][i] < dp[s][i]) {
            dp[s][i] = dp[s - (1 << i)][j] + cost[j][i];
            parent[s][i] = j;
          }
      }

    string ans;
    const vector<int>& dpBack = dp.back();
    int j = distance(dpBack.begin(), ranges::min_element(dpBack));
    int s = (1 << n) - 1;  // 2^0 + 2^1 + ... + 2^(n - 1)

    // Traverse back to build the string.
    while (s > 0) {
      const int i = parent[s][j];
      if (i == -1)
        ans = words[j] + ans;
      else
        ans = words[j].substr(words[j].length() - cost[i][j]) + ans;
      s -= 1 << j;
      j = i;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
  public String shortestSuperstring(String[] words) {
    final int n = words.length;
    // cost[i][j] := the cost to append words[j] after words[i]
    int[][] cost = new int[n][n];
    // Pre-calculate the `cost` array to save time.
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        cost[i][j] = getCost(words[i], words[j]);
        cost[j][i] = getCost(words[j], words[i]);
      }
    // dp[s][j] := the minimum cost to visit nodes of s ending in j, s is a
    // binary Value, e.g. dp[6][2] means the minimum cost to visit {1, 2} ending
    // in 2 (6 = 2^1 + 2^2)
    int[][] dp = new int[1 << n][n];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE / 2));
    // parent[s][j] := the parent of "nodes of s ending in j"
    int[][] parent = new int[1 << n][n];
    Arrays.stream(parent).forEach(A -> Arrays.fill(A, -1));

    for (int i = 0; i < n; ++i)
      dp[1 << i][i] = words[i].length();

    // Enumerate all the states ending in different nodes.
    for (int s = 1; s < (1 << n); ++s)
      for (int i = 0; i < n; ++i) {
        if ((s & (1 << i)) == 0)
          continue;
        for (int j = 0; j < n; ++j)
          if (dp[s - (1 << i)][j] + cost[j][i] < dp[s][i]) {
            dp[s][i] = dp[s - (1 << i)][j] + cost[j][i];
            parent[s][i] = j;
          }
      }

    String ans = "";
    int j = getLastNode(dp[(1 << n) - 1]);
    int s = (1 << n) - 1; // 2^0 + 2^1 + ... + 2^(n - 1)

    // Traverse back to build the string.
    while (s > 0) {
      final int i = parent[s][j];
      if (i == -1)
        ans = words[j] + ans;
      else
        ans = words[j].substring(words[j].length() - cost[i][j]) + ans;
      s -= 1 << j;
      j = i;
    }

    return ans;
  }

  // Returns the cost to append b after a.
  private int getCost(final String a, final String b) {
    int cost = b.length();
    final int minLength = Math.min(a.length(), b.length());
    for (int k = 1; k <= minLength; ++k)
      if (a.substring(a.length() - k).equals(b.substring(0, k)))
        cost = b.length() - k;
    return cost;
  }

  private int getLastNode(int[] row) {
    int minIndex = 0;
    for (int i = 1; i < row.length; ++i)
      if (row[i] < row[minIndex])
        minIndex = i;
    return minIndex;
  }
}