820. Short Encoding of Words

Leetcode link

解题思路

本题要求我们将一个字符串数组编码为一个用 # 区隔的长字符串

根据题目的描述，我们的出一个结论：当一个字符串是另一个字符串的后缀时，可以忽略它的长度

根据这个结论，我们可以使用字典树这个数据结构来求解

具体而言，我们可以用字符串倒叙的方式来组织字典树，举个例子：

数组 words 有两个元素 ['time', 'me', 'abe', 'el', bell]，按照字符串倒叙来组织字典树之后如下图所示

我们在组织完字典树的时候，顺便用变量 count 记录一下当前节点有多少子节点，比如 'me' 的 m 就有两个子节点

最后我们只需要判断 count 为 0 的字符串长度加一的总和就是我们的答案了

C++

class TrieNode {
    TrieNode* children[26];
public:
    int count;
    TrieNode() {
        for(int i = 0;i < 26;i++) {
            children[i] = nullptr;
        }
        count = 0;
    }
    TrieNode* add(char c) {
        if(children[c - 'a'] == nullptr) {
            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 < words.size();i++) {
            string word = words[i];
            TrieNode* cur = trie;
            for(int j = word.size() - 1;j >= 0;j--) {
                cur = cur->add(word[j]);
            }
            nodes[cur] = i;
        }

        int res = 0;
        for(auto& [node, idx]: nodes) {
            if(node->count == 0) {
                res += words[idx].size() + 1;
            }
        }

        return res;
    }
};