💥 TypeScript | Runtime beats 100.00%, Memory beats 75.00% [EXPLAINED]
Intuition\nI need to form the shortest string containing all given words by overlapping them as much as possible. It\'s like fitting words together with maximum
# Intuition\nI need to form the shortest string containing all given words by overlapping them as much as possible. It\'s like fitting words together with maximum overlap to minimize the total length.\n\n\n# Approach\nEach bit in the mask tracks which words are included. I calculate the overlap between every word pair and use DP to combine words in the most efficient order. Then, I reconstruct the shortest superstring from the DP results.\n\n\n# Complexity\n- Time complexity:\nO(n^2 * 2^n * l), where n is the number of words and l is the average word length.\n\n\n- Space complexity:\nO(n * 2^n) for storing DP and paths.\n\n\n# Code\n```typescript []\nfunction shortestSuperstring(words: string[]): string {\n    const n = words.length;\n    \n    // Step 1: Calculate the overlap between each pair of words\n    const overlap: number[][] = Array.from({ length: n }, () => Array(n).fill(0));\n    for (let i = 0; i < n; i++) {\n        for (let j = 0; j < n; j++) {\n            if (i !== j) {\n                overlap[i][j] = getOverlap(words[i], words[j]);\n            }\n        }\n    }\n\n    // Step 2: Initialize DP and parent tables\n    const dp: number[][] = Array.from({ length: 1 << n }, () => Array(n).fill(Infinity));\n    const parent: number[][] = Array.from({ length: 1 << n }, () => Array(n).fill(-1));\n\n    for (let i = 0; i < n; i++) {\n        dp[1 << i][i] = words[i].length;\n    }\n\n    // Step 3: Fill DP table using bitmasking\n    for (let mask = 1; mask < (1 << n); mask++) {\n        for (let i = 0; i < n; i++) {\n            if ((mask & (1 << i)) === 0) continue;  // skip if word `i` is not in the mask\n            const prevMask = mask ^ (1 << i);  // remove the current word from mask\n            for (let j = 0; j < n; j++) {\n                if ((prevMask & (1 << j)) === 0) continue;  // skip if word `j` is not in the mask\n                const newLength = dp[prevMask][j] + overlap[j][i];\n                if (newLength < dp[mask][i]) {\n                    dp[mask][i] = newLength;\n                    parent[mask][i] = j;\n                }\n            }\n        }\n    }\n\n    // Step 4: Find the minimum length superstring\n    let lastWord = -1;\n    let minLength = Infinity;\n    const finalMask = (1 << n) - 1;\n\n    for (let i = 0; i < n; i++) {\n        if (dp[finalMask][i] < minLength) {\n            minLength = dp[finalMask][i];\n            lastWord = i;\n        }\n    }\n\n    // Step 5: Reconstruct the shortest superstring\n    let mask = finalMask;\n    const sequence: number[] = [];\n\n    while (mask > 0) {\n        sequence.push(lastWord);\n        const prev = lastWord;\n        lastWord = parent[mask][lastWord];\n        mask ^= (1 << prev);  // remove the last word from the mask\n    }\n\n    sequence.reverse();  // reverse the sequence to get the correct order\n\n    // Step 6: Build the superstring using the sequence and overlaps\n    let result = words[sequence[0]];\n    for (let i = 1; i < sequence.length; i++) {\n        const overlapLen = overlap[sequence[i - 1]][sequence[i]];\n        result += words[sequence[i]].substring(words[sequence[i]].length - overlapLen);\n    }\n\n    return result;\n}\n\n// Helper function to calculate the overlap between two words\nfunction getOverlap(a: string, b: string): number {\n    for (let len = Math.min(a.length, b.length); len > 0; len--) {\n        if (a.endsWith(b.substring(0, len))) {\n            return b.length - len;\n        }\n    }\n    return b.length;\n}\n\n```
['TypeScript']