题目描述

传送门-力扣

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。
对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
-输入: words = ["time", "me", "bell"]
-输出: 10
-说明: S = "time#bell#" ， indexes = [0, 2, 5] 。

思路

1.后缀法

当限定了单词的长度不超过某个较小的数字时，可以用过遍历每个单词的1到str.length()-1个单词组成的后缀是否在所给的单词列表中，如果存在则可以直接将该单词抹除掉，然后计算全部单词的长度+1的和即可。

代码
class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        set<string> myset(words.begin(), words.end());
        for(int i = 0; i < words.size(); i++)
            for(int j = 1; j < words[i].size(); j++)
                myset.erase(words[i].substr(j));

        int len = 0;
        for(const string &word : myset)
            len += word.length() + 1;
        return len;
    }
};

.
.
.
.

2.字典树（前缀树、Trie树）

当不限定单词长度时，使用后缀法具有较高的时间复杂度，因此可以用字典树来优化时间复杂度。
为了找出不同单词是否具有相同的后缀，需要将单词反向插入到字典树中，例如，我们有 "time" 和 "me"，可以将 "emit" 和 "em" 插入字典树中。
图片说明

步骤

  1. 首先需要定义字典树的结构，只考虑小写字符的情况下，共26个字符，因此相当于一个26叉树

    class Trie
{
 Trie *child[26];
 Trie()
 {
     for(int i = 0; i < 26; i++)
         child[i] = nullptr;
 }
};

  2. 接下来，需要在字典树中进行字符的插入,从单词最后一位开始向前遍历，当该字母对应的位置为空，就在该处创建一个节点作为父节点，继续在该节点的基础上处理字符串中的前一个字符。

    void insert(Trie* root, string word)
{
    Trie* tmp = root;
    for(int i = word.length() - 1; i >= 0; i--)
    {
        if( tmp->child[word[i]-'a'] == nullptr) //没有该字符的节点就创建节点
            tmp->child[word[i]-'a'] = new Trie();
        tmp = tmp->child[word[i]-'a'];          //这里相当于递归，在该节点后面继续创建节点
    }
}

  3. 创建好字典树后，需要遍历字典树来计算全部节点的个数，采用深度优先搜索进行遍历。设置一个结束标志位，当还有子树时，标志位置为false，没有子树时，即为该条路径遍历结束，保存树的深度。

    void dfs(Trie *root, int &ans, int deep)
{   
    bool endFlag = true;
    for(int i = 0; i < 26; i++)
    {
        if(root->child[i] != nullptr)
        {
            dfs(root->child[i], res, deep + 1); //递归调用，记得深度+1
            endFlag = false;
        }
    }
    if(endFlag) res += deep;    //叶子节点，结果加上当前深度
}

  4. 程序主体,因为字典树的一条路径上字符的数量是节点数-1的，因此如果只是计算字符个数，那么dfs()应该从0开始，而这里因为每个单词后会有一个结束符，占用一个字符，因此是从1开始。

    int minimumLengthEncoding(vector<string>& words) {
    Trie * root = new Trie();        //创建一棵字典树
    for(int i = 0; i < words.size(); i++)
        insert(root, words[i]);      //插入

    int ans= 0;
    dfs(root, ans, 1);               //从1开始
    return ans;
}

  5. 全部代码

    class Trie
{
public:
    Trie *childen[26];
    Trie()
    {
        for(int i = 0; i < 26; i++)
            childen[i] = nullptr;
    }
};
//
//
class Solution {
public:
 int minimumLengthEncoding(vector<string>& words) {
     Trie *root = new Trie();
     for(const string &word : words)
         insert(root, word);

     int ans = 0;
     dfs(root, ans, 1);
     return ans;
 }

 void insert(Trie *root, string word)
 {
     Trie *temp = root;
     for(int i = word.length() - 1; i >= 0; i--)
     {
         if(temp->childen[word[i] - 'a'] == nullptr)
             temp->childen[word[i] - 'a'] = new Trie();
         temp = temp->childen[word[i] - 'a'];
     }
 }

 void dfs(Trie *root, int &ans, int deep)
 {
     bool endFlag = true;
     for(int i = 0; i < 26; i++)
     {
         if(root->childen[i] != nullptr)
         {
             dfs(root->childen[i], ans, deep + 1);
             endFlag = false;
         }
     }
     if(endFlag)
         ans += deep;
 }
};

```