题目:
难度:Middle
相关话题:设计
、字典树
、回溯算法
设计一个支持以下两种操作的数据结构:
void addWord(word)
bool search(word)
search(word)可以搜索文字或正则表达式字符串,字符串只包含字母 .
或 a-z
。 .
可以表示任何一个字母。
示例:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
说明:
你可以假设所有单词都是由小写字母 a-z
组成的。
思路:
先构建Tire
树,可以简单的用{}
嵌套构成。
addWord
中,将单词每个字母添加到tire
中,最后一个字母添加结尾标志。
search
中,对每一个字符搜索,如果存在则进入更深一层继续搜索,其中.
可以代表任意值,需要遍历当前tire
所有的字母都尝试一遍,直到找到对应单词。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* Initialize your data structure here.
*/
var WordDictionary = function() {
this.tire={}
};
/**
* Adds a word into the data structure.
* @param {string} word
* @return {void}
*/
WordDictionary.prototype.addWord = function(word) {
let t=this.tire
for(let i=0;i<word.length;i++){
let l=word[i]
if(t[l]==null)t[l]={}
if(i===word.length-1)t[l]['exact']=true
t=t[l]
}
};
/**
* Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
* @param {string} word
* @return {boolean}
*/
WordDictionary.prototype.search = function(word) {
function dfs(tire,idx){
if(idx===word.length){
return tire.exact
}
let l=word[idx]
if(l==='.'){
for(let k in tire){
if(dfs(tire[k],idx+1))return true
}
}else{
if(tire[l]==null)return false
if(dfs(tire[l],idx+1))return true
}
return false
}
return dfs(this.tire,0)
};
/**
* Your WordDictionary object will be instantiated and called as such:
* var obj = new WordDictionary()
* obj.addWord(word)
* var param_2 = obj.search(word)
*/