Shortest common superstring

Given a set of strings, A of length N.

Return the length of smallest string which has all the strings in the set as substring.



Input Format:

The first and the only argument has an array of strings, A.
Output Format:

Return an integer representing the minimum possible length of the resulting string.
Constraints:

1 <= N <= 18
1 <= A[i] <= 100
Example:

Input 1:
    A = ["aaaa", "aa"]

Output 1:
    4

Explanation 1:
    Shortest string: "aaaa"

Input 2:
    A = ["abcd", "cdef", "fgh", "de"]

Output 2:
    8

Explanation 2:
    Shortest string: "abcdefgh"

Method:

https://leetcode.com/problems/find-the-shortest-superstring/discuss/194932/Travelling-Salesman-Problem

Solution:

Time: O(n^2 * 2^n)
Space: O(n^2)

public class Solution {
        
    private int calc(String a, String b) {
        for (int i = 1; i < a.length(); i++) {
            if (b.startsWith(a.substring(i))) {
                return b.length() - a.length() + i;
            }
        }
        return b.length();
    }
    
    public int solve(String[] A) {
        int n = A.length;
        int[][] graph = new int[n][n];
        // build the graph
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = calc(A[i], A[j]);
                graph[j][i] = calc(A[j], A[i]);
            }
        }
        int[][] dp = new int[1 << n][n];
        int[][] path = new int[1 << n][n];
        int last = -1, min = Integer.MAX_VALUE;
        
        // start TSP DP
        for (int i = 1; i < (1 << n); i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) {
                    int prev = i - (1 << j);
                    if (prev == 0) {
                        dp[i][j] = A[j].length();
                    } else {
                        for (int k = 0; k < n; k++) {
                            if (dp[prev][k] < Integer.MAX_VALUE && dp[prev][k] + graph[k][j] < dp[i][j]) {
                                dp[i][j] = dp[prev][k] + graph[k][j];
                                path[i][j] = k;
                            }
                        }
                    }
                }
                if (i == (1 << n) - 1 && dp[i][j] < min) {
                    min = dp[i][j];
                    last = j;
                }
            }
        }
        
        // build the path
        StringBuilder sb = new StringBuilder();
        int cur = (1 << n) - 1;
        Stack<Integer> stack = new Stack<>();
        while (cur > 0) {
            stack.push(last);
            int temp = cur;
            cur -= (1 << last);
            last = path[temp][last];
        }
        
        // build the result
        int i = stack.pop();
        sb.append(A[i]);
        while (!stack.isEmpty()) {
            int j = stack.pop();
            sb.append(A[j].substring(A[j].length() - graph[i][j]));
            i = j;
        }
        return sb.length();
    }
}

BFS:

public class Solution {
    private int overlap(String A, String B) {
        for (int i = 0; i < A.length(); i ++) {
            if (B.startsWith(A.substring(i))) {
                return A.length() - i;
            }
        }
        return 0;
    }
    
    private int shortestLength(String[] A, int[][] G, List<Integer> path) {
        int prevIndex = path.get(0);
        int length = A[prevIndex].length();
        for (int i = 1; i < path.size(); i ++) {
            int currIndex = path.get(i);
            int overlap = G[prevIndex][currIndex];
            length += A[currIndex].length() - overlap;
            prevIndex = currIndex;
        }
        return length;
    }

    static class Node {
        int mask;
        int currIndex;
        List<Integer> path;
        int pathLength;
        
        public Node(int mask, int currIndex, List<Integer> path, int pathLength) {
            this.mask = mask;
            this.currIndex = currIndex;
            this.path = path;
            this.pathLength = pathLength;
        }
    }

    public int solve(String[] A) {
        int n = A.length;
        int[][] G = new int[n][n];
        for (int i = 0; i < n; i ++) {
            for (int j = i + 1; j < n; j ++) {
                G[i][j] = overlap(A[i], A[j]);
                G[j][i] = overlap(A[j], A[i]);
            }
        }
        
        // dp[mask][curr_node]
        int[][] dp = new int[1 << n][n];
        Deque<Node> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i ++) {
            int mask = 1 << i;
            List<Integer> path = new ArrayList<>();
            path.add(i);
            queue.offer(new Node(mask, i, path, 0));
        }
        List<Integer> bestPath = new ArrayList<>();
        int longestPath = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            if (curr.pathLength < dp[curr.mask][curr.currIndex]) continue;
            if (curr.mask == (1 << n) - 1 && curr.pathLength > longestPath) {
                bestPath = curr.path;
                longestPath = curr.pathLength;
            }
            for (int i = 0; i < n; i ++) {
                int nextMask = curr.mask | (1 << i);
                int nextPathLength = curr.pathLength + G[curr.currIndex][i];
                if (nextMask != curr.mask && nextPathLength >= dp[nextMask][i]) {
                    List<Integer> nextPath = new ArrayList<>(curr.path);
                    nextPath.add(i);
                    queue.offer(new Node(nextMask, i, nextPath, nextPathLength));
                }
            }
        }

        return shortestLength(A, G, bestPath);
    }
}