class Solution {
public:
   string shortestSuperstring(vector<string>& A) {
      //use g[i][j] represents # of extra chars we need to add to form A[i]A[j]
      //the problem is a travelling sales man problem, nemely, find the shortest path
      //to visited every node exactly once
      int n = A.size();
      vector<vector<int>> g(n, vector<int>(n, 0));
      for (int i = 0; i < n; ++i)
         for (int j = 0; j < n; ++j)
            if (i != j)
               g[i][j] = dist(A[i], A[j]);

      //dp[i][j] represents shortest path with visited node represented by i and and the
      //last node visited was j
      //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
      vector<vector<int>> dp(1 << n, vector<int>(n, 300));
      vector<vector<int>> parent(1 << n, vector<int>(n, -1));
      //init
      for (int i = 0; i < n; ++i)
         dp[1 << i][i] = A[i].size();
      int idx = -1, res = INT_MAX;
      for (int i = 1; i < (1 << n); ++i)
      {
         for (int j = 0; j < n; ++j)
         {
            if ((i & (1 << j)) == 0)continue;
            //get shortest path
            if (i == (1 << n) - 1 && dp[i][j] < res)
            {
               idx = j;
               res = dp[i][j];
            }
            for (int k = 0; k < n; ++k)
            {
               if (((1 << k) & i) == 0)
               {
                  if (g[j][k] + dp[i][j] < dp[i | (1 << k)][k])
                  {
                     dp[i | (1 << k)][k] = g[j][k] + dp[i][j];
                     parent[i | (1 << k)][k] = j;
                  }
               }
            }
         }
      }
      //reconstruct string
      string ss;
      int state = ((1 << n) - 1), curr = idx;
      while (state)
      {
         int prev = parent[state][curr];
         ss = (prev == -1? A[curr] : A[curr].substr(A[curr].size() - g[prev][curr])) + ss;
         state -= (1 << curr);
         curr = prev;
      }
      return ss;
   }

private:
   int dist(const string& s1, const string& s2)
   {
      int len1 = s1.size(), len2 = s2.size(), i = 1, clen = 0;
      while (i <= min(len1, len2))
      {
         if (s2.substr(0, i) == s1.substr(len1 - i))
            clen = i;
         ++i;
      }
      return s2.size() - clen;;
   }
};