Description
Given an array of words, encode them by appending # to form the shortest reference string. Return the minimum length.
Examples
words = ["time","me","bell"]10'me' is suffix of 'time', so encode as 'time#bell#' (10 chars). Suffix trie removes redundant words.
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]55The 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.
words = ["a","aa","aaa","aaaa"]5The 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