Find the Shortest Superstring LeetCode solution in C++

1
vector<vector<int>> dp, pre, par;
2

3
bool startWith(string s, string t) {
4
  // returns true if string s starts with string t
5
  int i;
6
  for (i = 0; i < s.length() && i < t.length(); i++) {
7
    if (s[i] == t[i])
8
      continue;
9
    else
10
      return false;
11
  }
12
  if (i == t.length())
13
    return true;
14
  else
15
    return false;
16
}
17

18
int calc(string A, string B) {
19
  // calculate the number of extra characters required to be appended to A
20
  // if A is followed by B
21
  // for eg. calc("abcd","cdef") = 2
22

23
  int a = A.length(), b = B.length();
24
  for (int i = 0; i < a; i++) {
25
    if (a - i <= b && startWith(B, A.substr(i))) {
26
      return b - (a - i);
27
    }
28
  }
29
  return b;
30
}
31

32
int finalMask, n;
33

34
int helper(int mask, int last) {
35
  // returns the minimum length of string required if last string appended was
36
  // A[last] the sets bit in mask represents the strings that were already
37
  // appended to the final string
38

39
  if (mask == finalMask) // all strings are appended in final string
40
    return 0;
41

42
  if (dp[mask][last] != -1) // memoization
43
    return dp[mask][last];
44

45
  int mn = INT_MAX;
46
  int p;
47
  for (int i = 0; i < n; i++) {
48
    if (mask & (1 << i)) continue;
49
    int cost = pre[last][i] + helper(mask | (1 << i),
50
                                     i); // extra characters need to be appended
51
    if (cost < mn) {
52
      mn = cost;
53
      p = i;
54
    }
55
  }
56
  par[mask][last] = p;        // store parent, so that it is easy to traceback and find
57
                              // the final result
58
  return dp[mask][last] = mn; // store result in DP table
59
}
60

61
class Solution {
62
 public:
63
  string shortestSuperstring(vector<string> &A) {
64
    n = A.size();
65
    pre.assign(n,
66
               vector<int>(n)); // for pre-computing calc(a,b) for all pairs of strings
67
    par.assign(1 << n, vector<int>(n, -1));
68
    for (int i = 0; i < n; i++) {
69
      for (int j = 0; j < n; j++) {
70
        if (j == i) continue;
71
        pre[i][j] = calc(A[i], A[j]);
72
      }
73
    }
74
    finalMask = (1 << n) - 1;
75
    dp.assign(1 << n, vector<int>(n, -1));
76
    int len = INT_MAX; // len will contain minimum length of required string
77
    int ind;
78
    for (int i = 0; i < n; i++) {
79
      int prev = len;
80
      len = min(len, (int)A[i].length() + helper(1 << i, i));
81
      if (len != prev) {
82
        ind = i;
83
      }
84
    }
85

86
    // Now traceback to find the final answer
87
    string ans = A[ind];
88
    int msk = 1 << ind;
89
    int prev_ind = ind;
90
    ind = par[msk][ind];
91
    while (ind != -1) {
92
      len = pre[prev_ind][ind];
93
      int alen = A[ind].length();
94
      ans += A[ind].substr(alen - len, len);
95
      msk = msk ^ (1 << ind);
96
      prev_ind = ind;
97
      ind = par[msk][ind];
98
    }
99
    return ans;
100
  }
101
};