【leetcode】【剑指offer Ⅱ】065. 最短的单词编码

问题描述：

• 单词数组 words 的有效编码由任意助记字符串 s 和下标数组 indices 组成，且满足：
  • words.length == indices.length。
  • 助记字符串 s 以 "#" 字符结尾。
  • 对于每个下标 indices[i]，s 的一个从 indices[i] 开始、到下一个 "#" 字符结束（但不包括 "#"）的子字符串恰好与 words[i] 相等。
• 给定一个单词数组 words，返回成功对 words 进行编码的最小助记字符串 s 的长度。

核心思路：

• 该题的题目不好理解，其实就是把同一后缀的多个单词保留下长度最长的一个。
• 该题仍然是前缀树的应用题。
  • 可以考虑首先将单词数组 words 排序，排序规则是单词长度越短排得越前。
  • 然后将单词数组中的所有单词都存入前缀树中，也就是说根据单词长度来进行插入前缀树操作，之所以要先将单词短的存入前缀树中，是因为要先将更短的单词存入，后续插入的单词需要判断其后缀是否已经被插入前缀树中。
  • 过程中用哈希表保存同一后缀的多个单词保留下长度最长的一个即可。
• 官方的题解同样是前缀树 + 哈希表，不过后半段方法中有所不同。
  • 首先前缀树实现中保存一个变量 count，当 count 值为 0，说明该节点为前缀树的叶子节点。
  • 接着把所有的单词都存入前缀树中（注意单词是从后往前遍历插入，即该前缀树实际上是后缀树），把插入过程中的每个结尾节点存进哈希表中。【关键在于：如果单词 a 是单词 b 的后缀，则单词 a 在树中的结尾节点 count != 0】
  • 最后就是遍历哈希表，判断该节点中的 count 是否为 0，如果为 0，则计算进最后结果中。

代码实现：

• 初始思路代码实现如下：

  class Trie
  {
  public:
      vector<Trie*> next;
      string prefix;
      Trie(): next(26) {}
  };
  
  class Solution
  {
  private:
      Trie* root;
  public:
      int minimumLengthEncoding(vector<string>& words)
      {
          sort(words.begin(), words.end(), [&](const string& a, const string& b)
          {
              return a.size() < b.size();
          });
          for(auto& word : words)
              reverse(word.begin(), word.end());
          root = new Trie();
          unordered_set<string> ss;
          for(auto& word : words)
          {
              Trie* cur = root;
              for(char& c : word)
              {
                  if(!cur->next[c-'a']) cur->next[c-'a'] = new Trie();
                  cur = cur->next[c - 'a'];
                  if(cur->prefix.size() > 0) if(ss.count(cur->prefix)) ss.erase(cur->prefix);
              }
              cur->prefix = word;
              ss.insert(word);
          }
          int ans = ss.size();
          for(auto& word : ss) ans += word.size();
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40

• 官方题解代码实现如下：【更简洁】

  class TrieNode{
      TrieNode* children[26];
  public:
      int count;
      TrieNode() {
          for (int i = 0; i < 26; ++i) children[i] = NULL;
          count = 0;
      }
      TrieNode* get(char c) {
          if (children[c - 'a'] == NULL) {
              children[c - 'a'] = new TrieNode();
              count++;
          }
          return children[c - 'a'];
      }
  };
  class Solution {
  public:
      int minimumLengthEncoding(vector<string>& words) {
          TrieNode* trie = new TrieNode();
          unordered_map<TrieNode*, int> nodes;
  
          for (int i = 0; i < (int)words.size(); ++i) {
              string word = words[i];
              TrieNode* cur = trie;
              for (int j = word.length() - 1; j >= 0; --j)
                  cur = cur->get(word[j]);
              nodes[cur] = i;
          }
  
          int ans = 0;
          for (auto& [node, idx] : nodes) {
              if (node->count == 0) {
                  ans += words[idx].length() + 1;
              }
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39