Short Encoding of Words
A valid encoding of an array of words is any reference string s and array of indices indices such that:
words.length == indices.length- The reference string
sends with the'#'character. - For each index
indices[i], the substring ofsstarting fromindices[i]and up to, but not including, the next'#'character is equal towords[i].
Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.
Example 1
Input
words = ["time","me","bell"]Output
10A shortest valid encoding is
"time#bell#", where "time", "me", and "bell" can be recovered starting at indices 0, 2, and 5 respectively.Example 2
Input
words = ["t"]Output
2A valid shortest encoding is
"t#", which has length 2.Constraints
- 1 <= words.length <= 2000
- 1 <= words[i].length <= 7
- words[i] consists of only lowercase letters.