daily pastebin goal
14%
SHARE
TWEET

Untitled

a guest Nov 21st, 2018 80 Never
Upgrade to PRO!
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. OK, I Understand
 
Top