给定一个单词列表,我们将这个列表编码成一个索引字符串 S
与一个索引列表 A
。
例如,如果这个列表是 ["time", "me", "bell"]
,我们就可以将其表示为 S = "time#bell#"
和 indexes = [0, 2, 5]
。
对于每一个索引,我们可以通过从字符串 S 中索引的位置开始读取字符串,直到 "#" 结束,来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢?
提示:
•1 <= words.length <= 200
•1 <= words[i].length <= 7
•每个单词都是小写字母 。
方法一:遍历后缀,hash检索
我们将数据存放在一个容器中,然后逐个拿出,检测拿出的字符串是否存在后缀在原容器中,如果存在,则删除,不存在则继续查看更小后缀,直至对比完该字符串,转而从容器拿出下一个元素,直至所有元素均检测完,处理并返回结果。
这个容器是散列集合 Set
,动画演示,转自LeetCode
时间复杂度:O(∑w^2) 其中 w 是 words[i]
的长度
空间复杂度:O(∑w)
方法二:Trie/字典树/前缀树
关于前缀树算法题,可见:LeetCode208. 实现 Trie (前缀树)[2]
假设我们现在给定字符串数组:"A", "to", "tea", "ted", "ten", "i", "in", "inn"
这颗树怎么理解呢?根节点无内容,读取第一个元素 A
加入这颗树,结果为:{A: {}}
,读取第二个字符串 to
,构造出 {t:{o:{}}, A:{}}
,继续读取第三个元素,构造出:{t:{o:{}, e: {a: {}}}, A:{}}
。以此类推,将所有元素存放进树中。代码实现如下:
/**
* 初始化树.
*/
var Trie = function() {
this.root = {}
};
/**
* 将元素添加到树汇总
*/
Trie.prototype.insert = function(word) {
let cur = this.root
for (i = 0; i < word.length; i++) {
const char = word.charAt(i)
if (!cur[char]) {
cur[char] = {}
}
cur = cur[char]
}
cur.isWord = true
};
/**
* 搜索树中是否含有某给定字符串
*/
Trie.prototype.search = function(word) {
let cur = this.root
for (i = 0; i < word.length; i++) {
const char = word.charAt(i)
if (!cur[char]) {
return false
}
cur = cur[char]
}
return cur.isWord || false
};
/**
* 搜索树中是否含有以给定字符串为前缀
*/
Trie.prototype.startsWith = function(prefix) {
let cur = this.root
for (i = 0; i < prefix.length; i++) {
const char = prefix.charAt(i)
if (!cur[char]) {
return false
}
cur = cur[char]
}
return true
};
有了前缀树的概念,我们再来解这道题似乎很简单了。
针对本题,我们不是看各字符串的公共前缀,而是看后缀,怎么理解呢?我们看一张图,转自LeetCode
我们把所有字符串先反转,然后存到字典树,查找时,我们只用统计根节点到叶子节点的节点个数+1的总和,即可知道字符串压缩后的长度
方法一:遍历后缀,hash检索
/**
* @param {string[]} words
* @return {number}
*/
var minimumLengthEncoding = function(words) {
const wordSet = new Set(words)
for (let word of words) {
for (let i = 1; i < word.length; i++) {
wordSet.delete(word.substring(i))
}
}
return [...wordSet].join('#').length + 1
};
方法二:Trie/字典树/前缀树
/**
* @param {string[]} words
* @return {number}
*/
var minimumLengthEncoding = function (words) {
const trie = new Trie()
let len = 0
const cwords = words.sort((a, b) => b.length - a.length);
for (let word of cwords) {
len += trie.insert(word)
}
return len
};
var Trie = function () {
this.root = {}
};
Trie.prototype.insert = function (word) {
let cur = this.root
let isNew = false
for (i = word.length - 1; i >= 0; i--) {
const char = word.charAt(i)
if (!cur[char]) {
isNew = true
cur[char] = {}
}
cur = cur[char]
}
return isNew ? word.length + 1 : 0
};
1.Function.prototype.apply和Function.prototype.call 的作用是一样的,区别在于传入参数的不同;2.第一个参数都是,指定函数体内this的指向;3.第二个参数不同,apply是传入带下标的集合,数组或者类数组,apply把它传给函数作为参数。call从第二个开始传入的参数是不固定的,都会传给函数作为参数。4.call比apply的性能要好,平常可以多用call, call传入参数的格式正是内部所需要的格式
[1]
820. 单词的压缩编码: https://leetcode-cn.com/problems/short-encoding-of-words/
[2]
208. 实现 Trie (前缀树): https://leetcode-cn.com/problems/implement-trie-prefix-tree/
本文分享自 JavaScript全栈 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!