• API
• FAQ
• Tools
• Archive
daily pastebin goal
14%
SHARE
TWEET

# Untitled

a guest Nov 21st, 2018 80 Never
ENDING IN00days00hours00mins00secs

1. class Solution {
2. public:
3.    string shortestSuperstring(vector<string>& A) {
4.       //use g[i][j] represents # of extra chars we need to add to form A[i]A[j]
5.       //the problem is a travelling sales man problem, nemely, find the shortest path
6.       //to visited every node exactly once
7.       int n = A.size();
8.       vector<vector<int>> g(n, vector<int>(n, 0));
9.       for (int i = 0; i < n; ++i)
10.          for (int j = 0; j < n; ++j)
11.             if (i != j)
12.                g[i][j] = dist(A[i], A[j]);
13.
14.       //dp[i][j] represents shortest path with visited node represented by i and and the
15.       //last node visited was j
16.       //dp[i ^ (1 << k)][k] = min(dp[i][j] + g[j][k]), where k is not visited, j can be every node visited in i
17.       vector<vector<int>> dp(1 << n, vector<int>(n, 300));
18.       vector<vector<int>> parent(1 << n, vector<int>(n, -1));
19.       //init
20.       for (int i = 0; i < n; ++i)
21.          dp[1 << i][i] = A[i].size();
22.       int idx = -1, res = INT_MAX;
23.       for (int i = 1; i < (1 << n); ++i)
24.       {
25.          for (int j = 0; j < n; ++j)
26.          {
27.             if ((i & (1 << j)) == 0)continue;
28.             //get shortest path
29.             if (i == (1 << n) - 1 && dp[i][j] < res)
30.             {
31.                idx = j;
32.                res = dp[i][j];
33.             }
34.             for (int k = 0; k < n; ++k)
35.             {
36.                if (((1 << k) & i) == 0)
37.                {
38.                   if (g[j][k] + dp[i][j] < dp[i | (1 << k)][k])
39.                   {
40.                      dp[i | (1 << k)][k] = g[j][k] + dp[i][j];
41.                      parent[i | (1 << k)][k] = j;
42.                   }
43.                }
44.             }
45.          }
46.       }
47.       //reconstruct string
48.       string ss;
49.       int state = ((1 << n) - 1), curr = idx;
50.       while (state)
51.       {
52.          int prev = parent[state][curr];
53.          ss = (prev == -1? A[curr] : A[curr].substr(A[curr].size() - g[prev][curr])) + ss;
54.          state -= (1 << curr);
55.          curr = prev;
56.       }
57.       return ss;
58.    }
59.
60. private:
61.    int dist(const string& s1, const string& s2)
62.    {
63.       int len1 = s1.size(), len2 = s2.size(), i = 1, clen = 0;
64.       while (i <= min(len1, len2))
65.       {
66.          if (s2.substr(0, i) == s1.substr(len1 - i))
67.             clen = i;
68.          ++i;
69.       }
70.       return s2.size() - clen;;
71.    }
72. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top