Leetcode Problem 943. Find the Shortest Superstring

Algorithm

1. Precompute the overlap between every pair of words.
2. Initialize dp array with -1 and set dp[1<<i][i] to the length of the i-th word for all i.
3. Iterate over all masks from 0 to (1<<n)-1, where n is the number of words.
4. For each mask, iterate over all words i that are in the current combination (i.e., mask & (1<<i) != 0).
5. For each word i, iterate over all words j that are not in the current combination (i.e., mask & (1<<j) == 0).
6. Calculate the new mask by setting the j-th bit of the current mask.
7. Update dp[new_mask][j] with the maximum overlap by considering the overlap between words i and j.
8. After populating the dp array, backtrack from dp[(1<<n)-1][i] to find the sequence of words that leads to the minimum superstring length.
9. Construct the superstring from the sequence of words.