{"id":4343,"date":"2018-11-18T15:10:30","date_gmt":"2018-11-18T23:10:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4343"},"modified":"2019-05-17T17:07:02","modified_gmt":"2019-05-18T00:07:02","slug":"leetcode-943-find-the-shortest-superstring","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-943-find-the-shortest-superstring\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 943. Find the Shortest Superstring"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 943. Find the Shortest Superstring - \u5237\u9898\u627e\u5de5\u4f5c EP231\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/u_Wc4jwrp3Q?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Given an array A of strings, find any&nbsp;smallest string that contains each string in&nbsp;<code>A<\/code>&nbsp;as a&nbsp;substring.<\/p>\n<p>We may assume that no string in&nbsp;<code>A<\/code>&nbsp;is substring of another string in&nbsp;<code>A<\/code>.<\/p>\n<div>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">[\"alex\",\"loves\",\"leetcode\"]<\/span>\n<strong>Output: <\/strong><span id=\"example-output-1\">\"alexlovesleetcode\"<\/span>\n<strong>Explanation: <\/strong>All permutations of \"alex\",\"loves\",\"leetcode\" would also be accepted.\n<\/pre>\n<div>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-2-1\">[\"catg\",\"ctaagt\",\"gcta\",\"ttca\",\"atgcatc\"]<\/span>\n<strong>Output: <\/strong><span id=\"example-output-2\">\"gctaagttcatgcatc\"<\/span><\/pre>\n<\/div>\n<\/div>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>1 &lt;= A.length &lt;= 12<\/code><\/li>\n<li><code>1 &lt;= A[i].length &lt;= 20<\/code><\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4352\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/11\/943-ep231.png\" alt=\"\" width=\"960\" height=\"540\"><\/p>\n<h1><strong>Solution 1: Search +&nbsp;Pruning<\/strong><\/h1>\n<p>Try all permutations. Pre-process the cost from word[i] to word[j] and store it in g[i][j].<\/p>\n<p>Time complexity: O(n!)<\/p>\n<p>Space complexity: O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua, running time: 692 ms\nclass Solution {\npublic:\n  string shortestSuperstring(vector&lt;string&gt;&amp; A) {    \n    const int n = A.size();\n    g_ = vector&lt;vector&lt;int&gt;&gt;(n, vector&lt;int&gt;(n));\n    for (int i = 0; i &lt; n; ++i)\n      for (int j = 0; j &lt; n; ++j) {\n        g_[i][j] = A[j].length();\n        for (int k = 1; k &lt;= min(A[i].length(), A[j].length()); ++k)\n          if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))            \n            g_[i][j] = A[j].length() - k;\n      }\n    vector&lt;int&gt; path(n);\n    best_len_ = INT_MAX;\n    dfs(A, 0, 0, 0, path);    \n    string ans = A[best_path_[0]];\n    for (int k = 1; k &lt; best_path_.size(); ++k) {\n      int i = best_path_[k - 1];\n      int j = best_path_[k];\n      ans += A[j].substr(A[j].length() - g_[i][j]);\n    }\n    return ans;\n  }\nprivate:\n  vector&lt;vector&lt;int&gt;&gt; g_;\n  vector&lt;int&gt; best_path_;\n  int best_len_;\n  void dfs(const vector&lt;string&gt;&amp; A, int d, int used, int cur_len, vector&lt;int&gt;&amp; path) {\n    if (cur_len &gt;= best_len_) return;\n    if (d == A.size()) {\n      best_len_ = cur_len;\n      best_path_ = path;\n      return;\n    }\n    \n    for (int i = 0; i &lt; A.size(); ++i) {\n      if (used &amp; (1 &lt;&lt; i)) continue;      \n      path[d] = i;\n      dfs(A,\n          d + 1, \n          used | (1 &lt;&lt; i),\n          d == 0 ? A[i].length() : cur_len + g_[path[d - 1]][i],\n          path);\n    }\n  }\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua, 439 ms, 35.8MB\nclass Solution {\n  private int n;\n  private int[][] g;\n  private String[] a;\n  private int best_len;\n  private int[] path;\n  private int[] best_path;\n  \n  private void dfs(int d, int used, int cur_len) {\n    if (cur_len &gt;= best_len) return;\n    if (d == n) {\n      best_len = cur_len;\n      best_path = path.clone();\n      return;\n    }\n    \n    for (int i = 0; i &lt; n; ++i) {\n      if ((used &amp; (1 &lt;&lt; i)) != 0) continue;\n      path[d] = i;\n      dfs(d + 1, \n          used | (1 &lt;&lt; i), \n          d == 0 ? a[i].length() : cur_len + g[path[d - 1]][i]);\n    }\n  }\n  \n  public String shortestSuperstring(String[] A) {\n    n = A.length;\n    g = new int[n][n];\n    a = A;\n    for (int i = 0; i &lt; n; ++i)\n      for (int j = 0; j &lt; n; ++j) {\n        g[i][j] = A[j].length();\n        for (int k = 1; k &lt;= Math.min(A[i].length(), A[j].length()); ++k)\n          if (A[i].substring(A[i].length() - k).equals(A[j].substring(0, k)))\n            g[i][j] = A[j].length() - k;        \n      }\n    \n    path = new int[n];\n    best_len = Integer.MAX_VALUE;\n    \n    dfs(0, 0, 0);\n    \n    String ans = A[best_path[0]];\n    for (int k = 1; k &lt; n; ++k) {\n      int i = best_path[k - 1];\n      int j = best_path[k];\n      ans += A[j].substring(A[j].length() - g[i][j]);      \n    }\n    return ans;\n  }\n}\n<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: DP<\/strong><\/h1>\n<p>g[i][j] is the cost of appending word[j] after word[i], or weight of edge[i][j].<\/p>\n<p>We would like find the shortest path to visit each node from 0 to n &#8211; 1 once and only once this is called&nbsp;the Travelling sells man&#8217;s problem which is NP-Complete.<\/p>\n<p>We can solve it with DP that uses exponential time.<\/p>\n<p>dp[s][i] := min distance to visit nodes (represented as a binary state s) once and only once and the path ends with node i.<\/p>\n<p>e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1, the possible paths could be (0, 2, 1), (2, 0, 1).<\/p>\n<p>Time complexity: O(n^2 * 2^n)<\/p>\n<p>Space complexity: O(n * 2^n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua, running time: 20 ms\nclass Solution {\npublic:\n  string shortestSuperstring(vector&lt;string&gt;&amp; A) {        \n    const int n = A.size();\n    vector&lt;vector&lt;int&gt;&gt; g(n, vector&lt;int&gt;(n));\n    for (int i = 0; i &lt; n; ++i)\n      for (int j = 0; j &lt; n; ++j) {\n        g[i][j] = A[j].length();\n        for (int k = 1; k &lt;= min(A[i].length(), A[j].length()); ++k)\n          if (A[i].substr(A[i].size() - k) == A[j].substr(0, k)) \n            g[i][j] = A[j].length() - k;\n      }\n    \n    vector&lt;vector&lt;int&gt;&gt; dp(1 &lt;&lt; n, vector&lt;int&gt;(n, INT_MAX \/ 2));\n    vector&lt;vector&lt;int&gt;&gt; parent(1 &lt;&lt; n, vector&lt;int&gt;(n, -1));\n    \n    for (int i = 0; i &lt; n; ++i) dp[1 &lt;&lt; i][i] = A[i].length();\n    \n    for (int s = 1; s &lt; (1 &lt;&lt; n); ++s) {\n      for (int j = 0; j &lt; n; ++j) {\n        if (!(s &amp; (1 &lt;&lt; j))) continue;\n        int ps = s &amp; ~(1 &lt;&lt; j);\n        for (int i = 0; i &lt; n; ++i) {\n          if (dp[ps][i] + g[i][j] &lt; dp[s][j]) {\n            dp[s][j] = dp[ps][i] + g[i][j];\n            parent[s][j] = i;\n          }\n        }\n      }\n    }\n    \n    auto it = min_element(begin(dp.back()), end(dp.back()));\n    int j = it - begin(dp.back());\n    int s = (1 &lt;&lt; n) - 1;\n    string ans;\n    while (s) {\n      int i = parent[s][j];\n      if (i &lt; 0) ans = A[j] + ans;\n      else ans = A[j].substr(A[j].length() - g[i][j]) + ans;\n      s &amp;= ~(1 &lt;&lt; j);\n      j = i;\n    }\n    return ans;\n  } \n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given an array A of strings, find any&nbsp;smallest string that contains each string in&nbsp;A&nbsp;as a&nbsp;substring. We may assume that no string in&nbsp;A&nbsp;is substring of&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[18,437,217,436,42,435],"class_list":["post-4343","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dp","tag-hamiltonian-path","tag-hard","tag-npc","tag-search","tag-tsp","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4343","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4343"}],"version-history":[{"count":14,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4343\/revisions"}],"predecessor-version":[{"id":5200,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4343\/revisions\/5200"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4343"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4343"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4343"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}