820. Compressed coding of words

The title

Given A list of words, we encode the list as an index string S and an index list A. For example, if the list is [“time”, “me”, “bell”], we can represent it as S = “time#bell#” and indexes = [0, 2, 5]. For each index, we can restore our previous list of words by reading the string from the index position in string S until the “#” ends. So what is the minimum string length that can successfully encode a given list of words?

Train of thought

1. They’re asking forMinimum string lengthI don’t have to figure outIndex stringandThe index lists.
   
   So at this point we can think about whether we don’t have to getIndex stringandThe index listsYou can solve for thatMinimum string lengthMethods.
2. The answer is yes, simply delete the words that are included at the end of other words and add the length of the remaining words to the number of remaining words.

Code implementation

1. Since the length of the contained word must be less than or equal to another word, to determine whether the word is included in other words, it is necessary to find the word with the smallest length and the word with the largest length. Therefore, the array can be sorted from small to large first.
2. After sorting, you can loop from the first word to see if any words are included at the end.
3. How do you make the best loop judgment? In the second layer of the cycle can start from the last word judgment, until there is a match or the same subscript can exit the cycle.
4. You can get the final array by converting it to a string and taking the length plus one, or you can loop through to get the result.

5. var minimumLengthEncoding = function (words) {
   words.sort((a, b) = a.length - b.length);
   for (let i = 0; i < words.length; i++) {
     let j = words.length - 1;
     while (j > i) {
       if (words[j].lastIndexOf(words[i]) === words[j].length - words[i].length) {
         words.splice(i, 1);
         i--;
         break; } j--; }}return words.toString().length + 1;
   };
   Copy the code

6. As shown in figure:
   
   
   

   

   The code worked and beat 100% in memory, but the problem was that it was running too slowly. So how do you solve this? You can increase efficiency by sacrificing a little space.

7. The biggest problem is that it takes too long to determine whether a word is included in another word. What if we thought the other way around, by clipping the word from the beginning to the end to determine if the cropped string is a word in the list? This is ok, but it seems more troublesome than the previous solution, but don’t forgetES6Added a built-in object to theSet, similar to a hash table. You can look up words quickly.
8. Now you don’t need to sort. getSetObject iterates through each word, clipping each word, and matching the resulting clipped string to thisSetExists, exists will exist the word can be deleted.

9. var minimumLengthEncoding = function (words) {
     let setWords = new Set(words);
     for (const word of setWords) {
       for (let i = 1; i < word.length; i++){
         lettarget = word.slice(i); setWords.has(target) && setWords.delete(target); }}let len = 0;
     setWords.forEach(word= > len += word.length + 1);
     return len;
   };
   Copy the code

10. As shown in figure:

Here to share the end, the first time to write an article, write not good many forgive me, finally thank you