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>& A) {
    const int n = A.size();
    // cost[i][j] := cost to append A[j] after A[i]
    vector<vector<int>> cost(n, vector<int>(n));

    // GetCost(a, b) := 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(A[i], A[j]);
        cost[j][i] = getCost(A[j], A[i]);
      }

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

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

    string ans = A[bestPath[0]];

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

    return ans;
  }

 private:
  // Used: i-th bit means A[i] is used or not
  void dfs(const vector<string>& A, 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 == A.size()) {
      minLength = currLength;
      bestPath = path;
      return;
    }

    for (int i = 0; i < A.size(); ++i) {
      if (1 << i & used)
        continue;
      path.push_back(i);
      const int newLength =
          depth == 0 ? A[i].length() : currLength + cost[path[depth - 1]][i];
      dfs(A, cost, 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
class Solution {
  public String shortestSuperstring(String[] A) {
    final int n = A.length;
    // cost[i][j] := cost to append A[j] after A[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(A[i], A[j]);
        cost[j][i] = getCost(A[j], A[i]);
      }

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

    minLength = n * 20; // Given by problem

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

    StringBuilder sb = new StringBuilder(A[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(A[j].substring(A[j].length() - cost[i][j]));
    }

    return sb.toString();
  }

  private int minLength;

  // GetCost(a, b) := 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 A[i] is used or not
  private void dfs(String[] A, int[][] cost, List<Integer> path, List<Integer> bestPath, int used,
                   int depth, int currLength) {
    if (currLength >= minLength)
      return;
    if (depth == A.length) {
      minLength = currLength;
      bestPath.clear();
      for (final int node : path) {
        bestPath.add(node);
      }
      return;
    }

    for (int i = 0; i < A.length; ++i) {
      if ((1 << i & used) > 0)
        continue;
      path.add(i);
      final int newLength = depth == 0 ? A[i].length() : currLength + cost[path.get(depth - 1)][i];
      dfs(A, 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
65
class Solution {
 public:
  string shortestSuperstring(vector<string>& A) {
    const int n = A.size();
    // cost[i][j] := cost to append A[j] after A[i]
    vector<vector<int>> cost(n, vector<int>(n));
    // dp[s][j] := min cost to visit nodes of s ending w/ j, s is a binary
    // Value, e.g. dp[6][2] means the min cost to visit {1, 2} ending w/ 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 w/ j"
    vector<vector<int>> parent(1 << n, vector<int>(n, -1));

    // GetCost(a, b) := 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(A[i], A[j]);
        cost[j][i] = getCost(A[j], A[i]);
      }

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

    // Enumerate all states ending w/ different node
    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(), min_element(dpBack.begin(), dpBack.end()));
    int s = (1 << n) - 1;  // 2^0 + 2^1 + ... + 2^(n - 1)

    // Traverse back to build the string
    while (s) {
      const int i = parent[s][j];
      if (i == -1)
        ans = A[j] + ans;
      else
        ans = A[j].substr(A[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
72
class Solution {
  public String shortestSuperstring(String[] A) {
    final int n = A.length;
    // cost[i][j] := cost to append A[j] after A[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(A[i], A[j]);
        cost[j][i] = getCost(A[j], A[i]);
      }
    // dp[s][j] := min cost to visit nodes of s ending w/ j, s is a binary
    // Value, e.g. dp[6][2] means the min cost to visit {1, 2} ending w/ 2
    // (6 = 2^1 + 2^2)
    int[][] dp = new int[1 << n][n];
    Arrays.stream(dp).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE / 2));
    // parent[s][j] := the parent of "nodes of s ending w/ j"
    int[][] parent = new int[1 << n][n];
    Arrays.stream(parent).forEach(row -> Arrays.fill(row, -1));

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

    // Enumerate all states ending w/ different node
    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 = A[j] + ans;
      else
        ans = A[j].substring(A[j].length() - cost[i][j]) + ans;
      s -= 1 << j;
      j = i;
    }

    return ans;
  }

  // GetCost(a, b) := 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;
  }
}