Description
Given an array of words, encode them by appending # to form the shortest reference string. Return the minimum length.
Examples
Input:
words = ["time","me","bell"]Output:
10Explanation:
"time#bell#".
Input:
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]Output:
26Explanation:
The optimal encoding is "catsdogcats#dogcatsdog#hippopotamuses#". Words "cat" and "cats" are suffixes of "catsdogcats", "dog" is a suffix of "dogcatsdog", and "rat" is contained within "ratcatdogcat" which itself is a suffix of a longer constructed string, but the most efficient encoding uses the three separate strings totaling 26 characters.
Input:
words = ["a","aa","aaa","aaaa"]Output:
6Explanation:
The optimal encoding is "aaaa#". Since "a", "aa", and "aaa" are all suffixes of "aaaa", only need to include the longest string "aaaa" plus the delimiter "#", giving us a total length of 5 characters for the string plus 1 for the delimiter.
Constraints
- •
1 ≤ words.length ≤ 2000