原文链接: https://leetcode-cn.com/problems/iSwD2y

中文题目

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

• words.length == indices.length
• 助记字符串 s 以 '#' 字符结尾
• 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等

给定一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

 

示例 1：

复制

输入：words = ["time", "me", "bell"]
输出：10
解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"

示例 2：

复制

输入：words = ["t"]
输出：2
解释：一组有效编码为 s = "t#" 和 indices = [0] 。

 

提示：

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 7
• words[i] 仅由小写字母组成

 

注意：本题与主站 820 题相同： https://leetcode-cn.com/problems/short-encoding-of-words/

通过代码

高赞题解

思路和心得：

（一）无序结合+暴力删掉后缀

1.如果word的某个后缀 是 别的单词，把别的单词从集合中删除。

复制

[]
class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        us = set(words)
        for word in words:
            for i in range(1, len(word)):
                suffix = word[i: ]
                us.discard(suffix)
        
        res = 0
        for w in us:
            res += len(w)
            res += 1
        return res

复制

[]
class Solution 
{
public:
    int minimumLengthEncoding(vector<string>& words) 
    {
        unordered_set<string> us(words.begin(), words.end());
        for (string word: words)
        {
            for (int i = 1; i < word.size(); i ++)
            {
                string suffix = word.substr(i);
                us.erase(suffix);
            }
        }

        int res = 0;
        for (string  w: us)
        {
            res += w.size();
            res += 1;
        }
        return res;
    }       
};

复制

[]
class Solution 
{
    public int minimumLengthEncoding(String[] words) 
    {
        Set<String> us = new HashSet<>(Arrays.asList(words));
        for (String word : words)
        {
            for (int i = 1; i < word.length(); i ++)
            {
                String suffix = word.substring(i, word.length());
                us.remove(suffix);
            }
        }

        int res = 0;
        for (String w : us)
        {
             res += w.length();
             res += 1;
        }
        return res;
    }
}

（二）Trie树

1.值统计每条路径的长度即可。

复制

[]
class Trie:
    def __init__(self):
        self.child = [None for _ in range(26)]
        self.cnt = 0        #经过这个结点的单词个数

    def insert(self, word: str) -> None:
        root = self
        for c in word[::-1]:
            ID = ord(c) - ord('a')
            if root.child[ID] == None:
                root.child[ID] = Trie()
                root.cnt += 1
            root = root.child[ID]
        root.cnt += 1

    def search(self, word: str) -> int:
        root = self
        for c in word[::-1]:
            ID = ord(c) - ord('a')
            root = root.child[ID]
        return root.cnt 


class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        T = Trie()

        words_us = set(words)

        for word in words_us:
            T.insert(word)
        
        res = 0
        for word in words_us:
            if T.search(word) == 1:       #是Trie树里一条路径最长的那个单词
                res += len(word) + 1
        return res

复制

[]
class Trie
{
public:
    Trie * child [26];
    int cnt;

    Trie()
    {
        memset(child, 0, sizeof(child));
        cnt = 0;
    }

    void insert(string word)
    {
        Trie * root = this;;
        for (int i = (int)word.size() -1; i > -1; i --)
        {
            int ID = word[i] - 'a';
            if (root->child[ID] == nullptr)
            {
                root->child[ID] = new Trie();
                root->cnt ++;
            }
            root = root->child[ID];
        }
        root->cnt ++;
    }

    int search(string word)
    {
        Trie * root = this;
        for (int i = (int)word.size() - 1 ; i > -1;  i --)
        {
            int ID = word[i] - 'a';
            root = root->child[ID];
        }
        return root->cnt;
    }

};

class Solution 
{
public:
    int minimumLengthEncoding(vector<string>& words) 
    {
        unordered_set<string> us(words.begin(), words.end());

        Trie * T = new Trie();

        for (string word : us)
            T->insert(word);
        
        int res = 0;
        for (string word : us)
            if (T->search(word) == 1)
                res += (int)word.size() + 1;
        
        return res;
    }
};

复制

[]
class Trie
{
    Trie [] child = new Trie [26];
    int cnt;

    Trie()
    {
        cnt = 0;
    }

    public void insert(String word)
    {
        Trie root = this;
        for (int i = word.length() - 1; i > -1; i --)
        {
            int ID = word.charAt(i) - 'a';
            if (root.child[ID] == null)
            {
                root.child[ID] = new Trie();
                root.cnt ++;
            }
            root = root.child[ID];
        }
        root.cnt ++;
    }

    public int search(String word)
    {
        Trie root = this;
        for (int i = word.length() - 1; i > -1; i --)
        {
            int ID = word.charAt(i) - 'a';
            root = root.child[ID];
        }
        return root.cnt;
    }

}

class Solution 
{
    public int minimumLengthEncoding(String[] words) 
    {
        Set<String> us = new HashSet(Arrays.asList(words));

        Trie T = new Trie();  
        for (String word : us)
            T.insert(word);
        
        int res = 0;
        for (String word : us)
        {
            if (T.search(word) == 1)
                res += word.length() + 1;
        }
        return res;

    }
}

统计信息

通过次数	提交次数	AC比率
1849	2876	64.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言