[LeetCode][JavaScript]Add and Search Word - Data structure design
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode][JavaScript]Add and Search Word - Data structure design，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2075字，纯文字阅读大概需要3分钟。
内容图文
Add and Search Word - Data structure design
Design a data structure that supports the following two operations:
void addWord(word) bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
https://leetcode.com/problems/add-and-search-word-data-structure-design/
字典树，在上一题的基础上稍做修改。http://www.cnblogs.com/Liok3187/p/4626730.html
遇到‘.‘就要采用递归的方式，遍历这一层词典里所有的词。
1
/*
*
2
* @constructor
3
*/
4
var WordDictionary = function() {
5this.root = new TrieNode(‘root‘);
6};
7 8function TrieNode(key) {
9return {
10 key : key,
11 isWord : false12 };
13}
1415/**
16 * @param {string} word
17 * @return {void}
18 * Adds a word into the data structure.
19*/20 WordDictionary.prototype.addWord = function(word) {
21var tree = this.root, i, curr;
22for(i = 0; i < word.length; i++){
23 curr = word[i];
24if(!tree[curr]){
25 tree[curr] = new TrieNode(curr);
26 }
27 tree = tree[curr];
28 }
29 tree.isWord = true;
30};
3132/**
33 * @param {string} word
34 * @return {boolean}
35 * Returns if the word is in the data structure. A word could
36 * contain the dot character ‘.‘ to represent any one letter.
37*/38 WordDictionary.prototype.search = function(word) {
39return searchWord(word, this.root);
4041function searchWord(word, tree){
42if(word === "" && tree.isWord){
43returntrue;
44 }
45if(word[0] !== ‘.‘){
46if(!tree[word[0]]){
47returnfalse;
48 }else{
49return searchWord(word.substring(1, word.length), tree[word[0]]);
50 }
51 }else{
52for(var i in tree){
53if(i === ‘key‘ || i === ‘isWord‘){
54continue;
55 }
56if(searchWord(word.substring(1, word.length), tree[i])){
57returntrue;
58 }
59 }
60returnfalse;
61 }
62 }
63 };
原文：http://www.cnblogs.com/Liok3187/p/4641498.html
内容总结
以上是互联网集市为您收集整理的[LeetCode][JavaScript]Add and Search Word - Data structure design全部内容，希望文章能够帮你解决[LeetCode][JavaScript]Add and Search Word - Data structure design所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。