Swift solution (Travelling Salesman Problem)
Swift version of https://leetcode.com/problems/find-the-shortest-superstring/discuss/194932/Travelling-Salesman-Problem\n\nclass Solution {\n    func shortestSu
Swift version of https://leetcode.com/problems/find-the-shortest-superstring/discuss/194932/Travelling-Salesman-Problem\n```\nclass Solution {\n    func shortestSuperstring(_ words: [String]) -> String {\n        let n = words.count, n2 = 1 << n\n\n        // build the graph\n        var graph = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)\n        for i in 0..<n {\n            forj: for j in 0..<n {\n                let ic = words[i].count, jc = words[j].count\n                for k in 0..<ic where words[j].starts(with: words[i].suffix(ic - k)) {\n                    graph[i][j] = jc - ic + k\n                    continue forj\n                }\n                graph[i][j] = jc\n            }\n        }\n\n        // start TSP DP\n        var dp = [[Int]](repeating: [Int](repeating: Int.max, count: n), count: n2), path = dp\n        for i in 1..<n2 {\n            for j in 0..<n where i & (1 << j) > 0 {\n                let prev = i - (1 << j)\n                if prev == 0 {\n                    dp[i][j] = words[j].count\n                } else {\n                    for k in 0..<n where dp[prev][k] < Int.max && dp[prev][k] + graph[k][j] < dp[i][j] {\n                        dp[i][j] = dp[prev][k] + graph[k][j]\n                        path[i][j] = k\n                    }\n                }\n            }\n        }\n\n        // build the path\n        var stack = [Int](), cur = n2 - 1, last = dp[n2 - 1].firstIndex(of: dp[n2 - 1].min()!)!\n        while cur > 0 {\n            stack.append(last)\n            (cur, last) = (cur - (1 << last), path[cur][last])\n        }\n\n        // build the result\n        var result = words[stack.last!]\n        for i in stride(from: stack.count - 2, through: 0, by: -1) {\n            let curWordIndex = stack[i], prevWordIndex = stack[i + 1]\n            result += String(words[curWordIndex].suffix(graph[prevWordIndex][curWordIndex]))\n        }\n\n        return result\n    }\n}\n```
['Swift']