“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Topic request

Topic describes

The effective encoding of words is composed of any mnemonic string S and subscript array indices, and satisfies:

Words.length == indices.length Mnemonic string s ends with ‘#’ character for each subscript indices[I], A substring of s starting with indices[I] and ending with the next ‘#’ character (but not including ‘#’) exactly equal to words[I] Given a word array words, return the length of the smallest mnemonic string S that successfully encodes words.

The sample

Example 1

Input: words = ["time", "me", "bell"] Output: 10 Explanation: a set of valid codes for S = "time#bell#" and indices = [0, 2, 5]. Words [0] = "time", s starts with substring from indices[0] = 0 to the end of next '#', as shown in bold "time#bell#" words[1] = "me", S starts with indices[1] = 2 and ends with the next '#' substring as shown in bold "time#bell#" words[2] = "bell", s starts with indices[2] = 5 and ends with the next '#' substring, As shown in bold: "time#bell#"Copy the code

Example 2

Input: words = ["t"] Output: 2 Explanation: a set of valid encoding s = "T #" and indices = [0].Copy the code

prompt

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 7
  • words[i]Consists of lowercase letters only

Their thinking

If the word a is a suffix of the word B, we can ignore the word A in our coding because we can encode the word A at the same time as we encode the word B. So we just need to traverse the list of words to determine whether other words are suffixes of the word currently traversed, and if so, remove the word from words.

In order to determine whether different words have the same suffix, we can put words in the dictionary number in reverse order. For example, if we have words’ test ‘and’ est ‘, we can insert ‘tset’ and ‘TSE’ into the tree. Then the leaf nodes of the dictionary number represent words without suffixes. Add the length of words together with the number of words, which is the result we seek.

code

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(a); count++; }return children[c - 'a']; }};class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        TrieNode* trie = new TrieNode(a); unordered_map<TrieNode*,int> nodes;

        for (int i = 0; i < (int)words.size(a); ++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; }}returnans; }};Copy the code