添加与搜索单词,数据结构设计。
Trie 称为数字树或前缀树,是一种搜索有序树数据结构,主要用于对字符串进行高效的动态添加/搜索操作。
应用:自动完成搜索、拼写检查、T9预测文本,IP路由(最长前缀匹配)等。
如果用hash实现的情况下,时间复杂度O(m * n)。大型数据集的缩放,一旦哈希表的增加,会有很多哈希冲突,搜索时间复杂度可以增加到 O(n ^ 2 * m),当存储具有许多相同前缀的键时,与hashmap相比,Trie可以使用更少的空间。
参考208,递归实现
- 时间复杂度O(n),空间复杂度O(1)
- Runtime: 204 ms, faster than 94.91%
- Memory Usage: 60.1 MB, less than 53.40%
var WordDictionary = function() {
this.map = {};
};
/**
* @param {string} word
* @return {void}
*/
WordDictionary.prototype.addWord = function(word) {
let node = this.map;
for (const ch of word) {
if (!node[ch]) {
node[ch] = {};
}
node = node[ch];
}
node.isEnd = true;
// console.log(this.map)
};
/**
* @param {string} word
* @return {boolean}
*/
WordDictionary.prototype.search = function(word) {
return this.searchInNode(word, this.map);
};
WordDictionary.prototype.searchInNode = function(word, node) {
for (let i = 0; i < word.length; i++) {
const ch = word[i];
if (!node[ch]) {
if (ch === '.') {
for (let j in node) {
if (this.searchInNode(word.substring(i + 1), node[j])) {
return true;
}
}
}
return false;
} else {
node = node[ch];
}
}
return node !== undefined && node.isEnd !== undefined;
};
/**
* Your WordDictionary object will be instantiated and called as such:
* var obj = new WordDictionary()
* obj.addWord(word)
* var param_2 = obj.search(word)
*/
网友评论