javascript use graph + bitmask dp
reference:\nhttps://leetcode.com/problems/find-the-shortest-superstring/discuss/195487/python-bfs-solution-with-detailed-explanation(with-extra-Chinese-explanat
reference:\nhttps://leetcode.com/problems/find-the-shortest-superstring/discuss/195487/python-bfs-solution-with-detailed-explanation(with-extra-Chinese-explanation)\nTLE fixed by @fdglchen\nhttps://leetcode.com/problems/find-the-shortest-superstring/discuss/195487/python-bfs-solution-with-detailed-explanation(with-extra-Chinese-explanation)/950172\n\nMain idea: Question can be transformed in this way, In a graph, start from a point, traverse all points, to make the path longest. use bfs\n\nRuntime: 5772ms a little slow.\n```\nconst getDistance2 = (s1, s2) => {\n    let n = s1.length;\n    for (let i = 1; i < n; i++) {\n        if (s2.startsWith(s1.slice(i))) return n - i + 1; // +1 to be able to handle edge 0\n    }\n    return 1;\n};\n\nconst getResFromPath2 = (w, G, path) => {\n    let res = w[path[0]];\n    let n = path.length;\n    for (let i = 1; i < n; i++) {\n        let [prev, cur] = [path[i - 1], path[i]];\n        let idx = G[prev][cur] - 1;  // -1 to handle edge 0\n        res += w[cur].slice(idx);\n    }\n    return res;\n};\n\nconst shortestSuperstring = (w) => {\n    let n = w.length;\n    let G = initialize2DArrayNew(n, n);\n    for (let i = 0; i < n; i++) {\n        for (let j = i + 1; j < n; j++) {\n            G[i][j] = getDistance2(w[i], w[j]);\n            G[j][i] = getDistance2(w[j], w[i]);\n        }\n    }\n    let dp = initialize2DArrayNew(1 << n, n);\n    let q = [];\n    for (let i = 0; i < n; i++) q.push([i, 1 << i, [i], 0]);\n    let maxDis = -1;\n    let p = [];\n    let final_mask = (1 << n) - 1;\n    while (q.length) { // bfs\n        let [node, mask, path, dis] = q.shift();\n        if (dis < dp[mask][node]) continue;\n        if (mask == final_mask && dis > maxDis) {\n            [p, maxDis] = [path, dis];\n            continue;\n        }\n        for (let i = 0; i < n; i++) {\n            if (1 << i & mask) continue;\n            let next_mask = mask | 1 << i;\n            let potential_overlap = dp[mask][node] + G[node][i];\n            if (potential_overlap > dp[next_mask][i]) { //  >= will TLE, have duplicated calculation. figured out by @fdglchen in original post comments\n                dp[next_mask][i] = potential_overlap;\n                q.push([i, next_mask, path.concat([i]), potential_overlap]);\n            }\n        }\n    }\n    return getResFromPath2(w, G, p);\n};\n\nconst initialize2DArrayNew = (n, m) => {\n    let data = [];\n    for (let i = 0; i < n; i++) {\n        let tmp = Array(m).fill(0);\n        data.push(tmp);\n    }\n    return data;\n};\n```\nSolution 2: Travelling salesman  https://en.wikipedia.org/wiki/Travelling_salesman_problem\nreference: https://leetcode.com/problems/find-the-shortest-superstring/discuss/194932/Travelling-Salesman-Problem\nRuntime: 152ms  90.07%\n```\nconst getDistance3 = (s1, s2) => {\n    let n = s1.length;\n    let m = s2.length;\n    for (let i = 1; i < n; i++) {\n        if (s2.startsWith(s1.slice(i))) return m - n + i;\n    }\n    return m;\n};\n\nconst getResFromPath3 = (w, G, p, last) => {\n    let n = w.length;\n    let res = \'\';\n    let cur = (1 << n) - 1;\n    let st = [];\n    while (cur > 0) {\n        st.push(last);\n        let tmp = cur;\n        cur -= 1 << last;\n        last = p[tmp][last];\n    }\n    let i = st.pop();\n    res += w[i];\n    while (st.length) {\n        let j = st.pop();\n        res += w[j].slice(w[j].length - G[i][j]);\n        i = j;\n    }\n    return res;\n};\n\nconst MAX = Number.MAX_SAFE_INTEGER;\nconst shortestSuperstring = (w) => {\n    let n = w.length;\n    let G = initialize2DArrayNew(n, n);\n    for (let i = 0; i < n; i++) {\n        for (let j = 0; j < n; j++) {\n            G[i][j] = getDistance3(w[i], w[j]);\n            G[j][i] = getDistance3(w[j], w[i]);\n        }\n    }\n    let dp = initialize2DArrayNew(1 << n, n);\n    let p = initialize2DArrayNew(1 << n, n);\n    let [last, min, final_mask] = [-1, MAX, (1 << n) - 1];\n    for (let i = 1; i < 1 << n; i++) {\n        dp[i].fill(MAX);\n        for (let j = 0; j < n; j++) {\n            if ((i & 1 << j) > 0) {\n                let prev = i - (1 << j);\n                if (prev == 0) {\n                    dp[i][j] = w[j].length;\n                } else {\n                    for (let k = 0; k < n; k++) {\n                        let potential_overlap = dp[prev][k] + G[k][j];\n                        if (dp[prev][k] < MAX && potential_overlap < dp[i][j]) {\n                            dp[i][j] = potential_overlap;\n                            p[i][j] = k;\n                        }\n                    }\n                }\n            }\n            if (i == final_mask && dp[i][j] < min) {\n                min = dp[i][j];\n                last = j;\n            }\n        }\n    }\n    return getResFromPath3(w, G, p, last);\n};\n\nconst initialize2DArrayNew = (n, m) => {\n    let data = [];\n    for (let i = 0; i < n; i++) {\n        let tmp = Array(m).fill(0);\n        data.push(tmp);\n    }\n    return data;\n};\n```
['Graph', 'Bitmask', 'JavaScript']