Frequencies of Shortest Supersequences
You are given an array of strings words. Find all shortest common supersequences (SCS) of words that are not permutations of each other.
A shortest common supersequence is a string of minimum length that contains each string in words as a subsequence.
Return a 2D array of integers freqs that represent all the SCSs. Each freqs[i] is an array of size 26, representing the frequency of each letter in the lowercase English alphabet for a single SCS. You may return the frequency arrays in any order.
Example 1
Input
words = ["ab","ba"]Output
[[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]The two SCSs are
"aba" and "bab"; the output is the letter frequencies for each one.Example 2
Input
words = ["aa","ac"]Output
[[2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]The two SCSs are
"aac" and "aca", and since they are permutations of each other, only one frequency array is kept.Constraints
- 1 <= words.length <= 256
- words[i].length == 2
- All strings in words will altogether be composed of no more than 16 unique lowercase letters.
- All strings in words are unique.