943. Find the Shortest Superstring

Question

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:

Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Note:

• 1 <= A.length <= 12
• 1 <= A[i].length <= 20

Solution:

• Method 1: search O(N! + N^2) AC 775ms
  • First create a cost[i][j] matrix, means the number of characters need to be added at the end of the result if last added word is A[i] and we want to add A[j]. Cost matrix is calculated at the very beginning so it will be calculated once, and its time efficiency is O(n^2).
  • We list all possible permutations and save the minimum. Pruning is required for remove useless iterations.
  • We only record the path of words it goes through and concat the string at the end(we only concat once).

      class Solution {
      public String shortestSuperstring(String[] A) {
          if(A.length == 1) return A[0];
          int[][] cost = new int[A.length][A.length];
          for(int i = 0; i < A.length; i++){
              LABEL:
              for(int j = 0; j < A.length; j++){
                  if(i == j){
                      cost[i][j] = A[j].length();
                  }else{
                      int start = A[i].indexOf(A[j].charAt(0));
                      if(start == -1) cost[i][j] = A[j].length();
                      else{
                          for(int k = start; k < A[i].length(); k++){
                              if(A[j].startsWith(A[i].substring(k))){
                                  cost[i][j] = A[j].length() - (A[i].length() - k);
                                  continue LABEL;
                              }
                          }
                          cost[i][j] = A[j].length();
                      }
                  }
              }
          }
          List<Integer> res = new ArrayList<>();
          dfs(A, cost, 0, 0, new ArrayList<Integer>(), res, 0);
          StringBuilder sb = new StringBuilder();
          for(int i = 0; i < res.size(); i++){
              Integer path = res.get(i);
              sb.append(i == 0 ? A[path]: A[path].substring(A[path].length() - cost[res.get(i - 1)][path]));
          }
          return sb.toString();
      }
      private int sum = Integer.MAX_VALUE;
      private void dfs(String[] A, int[][] cost, int index, int temp, List<Integer> path, List<Integer> res, int visited){
          if(temp >= sum) return;
          if(A.length == index){
              sum = temp;
              res.clear();
              res.addAll(path);
              return;
          }
          for(int i = 0; i < A.length; i++){
              if((visited & (1 << i)) > 0) continue;
              path.add(i);
              dfs(A,
                  cost,
                  index + 1,
                  index == 0 ? A[i].length(): temp + cost[path.get(index - 1)][i],
                  path,
                  res,
                  (visited | (1 << i)));
              path.remove(index);
          }
      }
      }
    

• Method 2: DP Need to fill when doing the dp questions.

Reference

1. 花花酱 LeetCode 943. Find the Shortest Superstring - 刷题找工作 EP231