单词的压缩编码算法详解编程语言
2023-06-13 09:11:47 时间
给定一个单词列表,我们将这个列表编码成一个索引字符串 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 = words.length = 2000
1 = words[i].length = 7
每个单词都是小写字母 。
解:这道题简单的做法是把所有字符存到一个哈希表里,然后遍历每个字符,从第二位开始尝试从哈希表里删除。
仔细理解这道题,能压缩的字符其实都是另一个字符的后缀,否则无法用下标表示,所以还对倒叙的字符,用字典序排序,再对两边相邻的做判断
字典树可以了解以下
class Solution { public: int minimumLengthEncoding(vector string words) { set string set_Str; for(auto iter:words) set_Str.insert(iter); for(auto iter:words) for(int i=1;i iter.size();i++) string tmp=iter.substr(i); set_Str.erase(tmp); int i=0; for(auto set_iter:set_Str) i+=set_iter.size()+1; return i; };
17566.html
cjava相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- 数据结构实验哈夫曼编码算法的实现_哈夫曼编码算法的实现
- 编码格式
- 【计算机网络】物理层 : 总结 ( 物理层特性 | 码元速率 | 通信方式 | 数据传输方式 | 信号类型 | 编码与调制 | 奈氏准则 | 香农定理 | 传输介质 | 物理层设备 ) ★★★
- Java 实现Huffman 编码算法详解编程语言
- 深入探究Linux查看文件编码格式的方法(linux编码格式查看)
- 编码Linux下设置UTF8编码的步骤(linux设置utf8)
- Linux 系统中 ANSI 编码的解释及应用简介(linuxansi)
- Linux下快速转换文件编码的实现方法(linux转换编码)
- asp下实现UrlEncoding转换编码的代码
- PHP字符串编码截取函数(兼容utf-8和gb2312)
- 修改mysql5.5默认编码(图文步骤修改为utf-8编码)
- asp中通过fso读取和生成UTF-8编码的txt
- JS与C#编码解码