Problem

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

Examples

Example 1

1
2
3

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

Example 2

1
2

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

Constraints

  • 1 <= words.length <= 12
  • 1 <= words[i].length <= 20
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

Solution

Method 1 – DP with Bitmask (Traveling Salesman Style)

Intuition

We want to join all words together with as much overlap as possible. This is similar to the Traveling Salesman Problem, where each word is a city and the cost is the extra length needed to add a word after another.

Approach

  1. Compute the maximum overlap between every pair of words.
  2. Use DP with bitmask: dp[mask][i] is the shortest superstring for set mask ending with word i.
  3. For each state, try to append a new word maximizing overlap.
  4. Reconstruct the answer from the DP table.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
public:
    string shortestSuperstring(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> overlap(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) if (i != j)
                for (int k = min(words[i].size(), words[j].size()); k > 0; --k)
                    if (words[i].substr(words[i].size()-k) == words[j].substr(0, k)) {
                        overlap[i][j] = k; break;
                    }
        vector<vector<int>> dp(1<<n, vector<int>(n, 0));
        vector<vector<int>> parent(1<<n, vector<int>(n, -1));
        for (int mask = 1; mask < (1<<n); ++mask) {
            for (int j = 0; j < n; ++j) {
                if (!(mask & (1<<j))) continue;
                int pmask = mask ^ (1<<j);
                if (pmask == 0) continue;
                for (int i = 0; i < n; ++i) {
                    if (!(pmask & (1<<i))) continue;
                    int val = dp[pmask][i] + overlap[i][j];
                    if (val > dp[mask][j]) {
                        dp[mask][j] = val;
                        parent[mask][j] = i;
                    }
                }
            }
        }
        int mask = (1<<n)-1, last = 0, best = -1;
        for (int i = 0; i < n; ++i)
            if (dp[mask][i] > best) { best = dp[mask][i]; last = i; }
        vector<int> path;
        while (last != -1) {
            path.push_back(last);
            int tmp = parent[mask][last];
            mask ^= (1<<last);
            last = tmp;
        }
        reverse(path.begin(), path.end());
        vector<bool> seen(n);
        string ans = words[path[0]];
        seen[path[0]] = true;
        for (int k = 1; k < path.size(); ++k) {
            int i = path[k-1], j = path[k];
            ans += words[j].substr(overlap[i][j]);
            seen[j] = true;
        }
        for (int i = 0; i < n; ++i) if (!seen[i]) ans += words[i];
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

func shortestSuperstring(words []string) string {
    n := len(words)
    overlap := make([][]int, n)
    for i := range overlap {
        overlap[i] = make([]int, n)
        for j := range overlap[i] {
            if i == j { continue }
            for k := min(len(words[i]), len(words[j])); k > 0; k-- {
                if words[i][len(words[i])-k:] == words[j][:k] {
                    overlap[i][j] = k; break
                }
            }
        }
    }
    dp := make([][]int, 1<<n)
    parent := make([][]int, 1<<n)
    for i := range dp {
        dp[i] = make([]int, n)
        parent[i] = make([]int, n)
        for j := range parent[i] { parent[i][j] = -1 }
    }
    for mask := 1; mask < 1<<n; mask++ {
        for j := 0; j < n; j++ {
            if mask&(1<<j) == 0 { continue }
            pmask := mask ^ (1<<j)
            if pmask == 0 { continue }
            for i := 0; i < n; i++ {
                if pmask&(1<<i) == 0 { continue }
                val := dp[pmask][i] + overlap[i][j]
                if val > dp[mask][j] {
                    dp[mask][j] = val
                    parent[mask][j] = i
                }
            }
        }
    }
    mask, last, best := (1<<n)-1, 0, -1
    for i := 0; i < n; i++ {
        if dp[mask][i] > best { best = dp[mask][i]; last = i }
    }
    path := []int{}
    for last != -1 {
        path = append(path, last)
        tmp := parent[mask][last]
        mask ^= 1 << last
        last = tmp
    }
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    seen := make([]bool, n)
    ans := words[path[0]]
    seen[path[0]] = true
    for k := 1; k < len(path); k++ {
        i, j := path[k-1], path[k]
        ans += words[j][overlap[i][j]:]
        seen[j] = true
    }
    for i := 0; i < n; i++ {
        if !seen[i] { ans += words[i] }
    }
    return ans
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    public String shortestSuperstring(String[] words) {
        int n = words.length;
        int[][] overlap = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) if (i != j)
                for (int k = Math.min(words[i].length(), words[j].length()); k > 0; --k)
                    if (words[i].endsWith(words[j].substring(0, k))) {
                        overlap[i][j] = k; break;
                    }
        int[][] dp = new int[1<<n][n];
        int[][] parent = new int[1<<n][n];
        for (int[] row : parent) Arrays.fill(row, -1);
        for (int mask = 1; mask < (1<<n); ++mask) {
            for (int j = 0; j < n; ++j) {
                if ((mask & (1<<j)) == 0) continue;
                int pmask = mask ^ (1<<j);
                if (pmask == 0) continue;
                for (int i = 0; i < n; ++i) {
                    if ((pmask & (1<<i)) == 0) continue;
                    int val = dp[pmask][i] + overlap[i][j];
                    if (val > dp[mask][j]) {
                        dp[mask][j] = val;
                        parent[mask][j] = i;
                    }
                }
            }
        }
        int mask = (1<<n)-1, last = 0, best = -1;
        for (int i = 0; i < n; ++i)
            if (dp[mask][i] > best) { best = dp[mask][i]; last = i; }
        List<Integer> path = new ArrayList<>();
        while (last != -1) {
            path.add(last);
            int tmp = parent[mask][last];
            mask ^= (1<<last);
            last = tmp;
        }
        Collections.reverse(path);
        boolean[] seen = new boolean[n];
        StringBuilder ans = new StringBuilder(words[path.get(0)]);
        seen[path.get(0)] = true;
        for (int k = 1; k < path.size(); ++k) {
            int i = path.get(k-1), j = path.get(k);
            ans.append(words[j].substring(overlap[i][j]));
            seen[j] = true;
        }
        for (int i = 0; i < n; ++i) if (!seen[i]) ans.append(words[i]);
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    fun shortestSuperstring(words: Array<String>): String {
        val n = words.size
        val overlap = Array(n) { IntArray(n) }
        for (i in 0 until n)
            for (j in 0 until n) if (i != j)
                for (k in minOf(words[i].length, words[j].length) downTo 1)
                    if (words[i].endsWith(words[j].substring(0, k))) {
                        overlap[i][j] = k; break
                    }
        val dp = Array(1 shl n) { IntArray(n) }
        val parent = Array(1 shl n) { IntArray(n) { -1 } }
        for (mask in 1 until (1 shl n)) {
            for (j in 0 until n) {
                if (mask and (1 shl j) == 0) continue
                val pmask = mask xor (1 shl j)
                if (pmask == 0) continue
                for (i in 0 until n) {
                    if (pmask and (1 shl i) == 0) continue
                    val v = dp[pmask][i] + overlap[i][j]
                    if (v > dp[mask][j]) {
                        dp[mask][j] = v
                        parent[mask][j] = i
                    }
                }
            }
        }
        var mask = (1 shl n) - 1
        var last = 0
        var best = -1
        for (i in 0 until n) if (dp[mask][i] > best) { best = dp[mask][i]; last = i }
        val path = mutableListOf<Int>()
        while (last != -1) {
            path.add(last)
            val tmp = parent[mask][last]
            mask = mask xor (1 shl last)
            last = tmp
        }
        path.reverse()
        val seen = BooleanArray(n)
        val ans = StringBuilder(words[path[0]])
        seen[path[0]] = true
        for (k in 1 until path.size) {
            val i = path[k-1]; val j = path[k]
            ans.append(words[j].substring(overlap[i][j]))
            seen[j] = true
        }
        for (i in 0 until n) if (!seen[i]) ans.append(words[i])
        return ans.toString()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution:
    def shortestSuperstring(self, words: list[str]) -> str:
        n = len(words)
        overlap = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i == j: continue
                for k in range(min(len(words[i]), len(words[j])), 0, -1):
                    if words[i][-k:] == words[j][:k]:
                        overlap[i][j] = k
                        break
        dp = [[0]*n for _ in range(1<<n)]
        parent = [[-1]*n for _ in range(1<<n)]
        for mask in range(1, 1<<n):
            for j in range(n):
                if not (mask & (1<<j)): continue
                pmask = mask ^ (1<<j)
                if pmask == 0: continue
                for i in range(n):
                    if not (pmask & (1<<i)): continue
                    val = dp[pmask][i] + overlap[i][j]
                    if val > dp[mask][j]:
                        dp[mask][j] = val
                        parent[mask][j] = i
        mask, last, best = (1<<n)-1, 0, -1
        for i in range(n):
            if dp[mask][i] > best:
                best = dp[mask][i]
                last = i
        path = []
        while last != -1:
            path.append(last)
            tmp = parent[mask][last]
            mask ^= (1<<last)
            last = tmp
        path = path[::-1]
        seen = [False]*n
        ans = words[path[0]]
        seen[path[0]] = True
        for k in range(1, len(path)):
            i, j = path[k-1], path[k]
            ans += words[j][overlap[i][j]:]
            seen[j] = True
        for i in range(n):
            if not seen[i]: ans += words[i]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

impl Solution {
    pub fn shortest_superstring(words: Vec<String>) -> String {
        let n = words.len();
        let mut overlap = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..n {
                if i == j { continue; }
                for k in (1..=words[i].len().min(words[j].len())).rev() {
                    if &words[i][words[i].len()-k..] == &words[j][..k] {
                        overlap[i][j] = k;
                        break;
                    }
                }
            }
        }
        let mut dp = vec![vec![0; n]; 1<<n];
        let mut parent = vec![vec![-1; n]; 1<<n];
        for mask in 1..1<<n {
            for j in 0..n {
                if mask & (1<<j) == 0 { continue; }
                let pmask = mask ^ (1<<j);
                if pmask == 0 { continue; }
                for i in 0..n {
                    if pmask & (1<<i) == 0 { continue; }
                    let val = dp[pmask][i] + overlap[i][j];
                    if val > dp[mask][j] {
                        dp[mask][j] = val;
                        parent[mask][j] = i as i32;
                    }
                }
            }
        }
        let (mut mask, mut last, mut best) = ((1<<n)-1, 0, -1);
        for i in 0..n {
            if dp[mask][i] > best { best = dp[mask][i]; last = i; }
        }
        let mut path = vec![];
        while last != -1 {
            path.push(last);
            let tmp = parent[mask][last];
            mask ^= 1 << last;
            last = if tmp == -1 { -1 } else { tmp as usize };
        }
        path.reverse();
        let mut seen = vec![false; n];
        let mut ans = words[path[0]].clone();
        seen[path[0]] = true;
        for k in 1..path.len() {
            let i = path[k-1]; let j = path[k];
            ans += &words[j][overlap[i][j]..];
            seen[j] = true;
        }
        for i in 0..n { if !seen[i] { ans += &words[i]; } }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    shortestSuperstring(words: string[]): string {
        const n = words.length;
        const overlap = Array.from({length: n}, () => Array(n).fill(0));
        for (let i = 0; i < n; i++)
            for (let j = 0; j < n; j++) if (i !== j)
                for (let k = Math.min(words[i].length, words[j].length); k > 0; k--)
                    if (words[i].endsWith(words[j].slice(0, k))) {
                        overlap[i][j] = k; break;
                    }
        const dp = Array.from({length: 1<<n}, () => Array(n).fill(0));
        const parent = Array.from({length: 1<<n}, () => Array(n).fill(-1));
        for (let mask = 1; mask < (1<<n); mask++) {
            for (let j = 0; j < n; j++) {
                if (!(mask & (1<<j))) continue;
                const pmask = mask ^ (1<<j);
                if (pmask === 0) continue;
                for (let i = 0; i < n; i++) {
                    if (!(pmask & (1<<i))) continue;
                    const val = dp[pmask][i] + overlap[i][j];
                    if (val > dp[mask][j]) {
                        dp[mask][j] = val;
                        parent[mask][j] = i;
                    }
                }
            }
        }
        let mask = (1<<n)-1, last = 0, best = -1;
        for (let i = 0; i < n; i++)
            if (dp[mask][i] > best) { best = dp[mask][i]; last = i; }
        const path: number[] = [];
        while (last !== -1) {
            path.push(last);
            const tmp = parent[mask][last];
            mask ^= (1<<last);
            last = tmp;
        }
        path.reverse();
        const seen = Array(n).fill(false);
        let ans = words[path[0]];
        seen[path[0]] = true;
        for (let k = 1; k < path.length; k++) {
            const i = path[k-1], j = path[k];
            ans += words[j].slice(overlap[i][j]);
            seen[j] = true;
        }
        for (let i = 0; i < n; i++) if (!seen[i]) ans += words[i];
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 * 2^n + n^3) where n is the number of words. The DP has O(n*2^n) states, and overlap computation is O(n^3).
  • 🧺 Space complexity: O(n*2^n) for DP and parent tables.