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
.
public class WordDictionary { public static class TrieNode { TrieNode[] children; boolean isLeaf; public TrieNode() { children = new TrieNode[26]; } } private TrieNode root = new TrieNode(); // Adds a word into the data structure. public void addWord(String word) { if(word == null || word.isEmpty()) return; TrieNode node = root; for(int i=0; i<word.length(); i++) { int j = word.charAt(i)-'a'; if(node.children[j] == null) { node.children[j] = new TrieNode(); } node = node.children[j]; } node.isLeaf = true; } // Returns if the word is in the data structure. A word could // contain the dot character '.' to represent any one letter. public boolean search(String word) { return search(root, word, 0); } private boolean search(TrieNode node, String word, int start) { if(node == null) return false; if(start == word.length()) return node.isLeaf; for(int i=start; i<word.length(); i++) { char c = word.charAt(i); if(c == '.') { for(int j=0; j<26; j++) { if(search(node.children[j], word, i+1)) return true; } return false; } else { // node = node.children[c-'a']; // if(node == null) return false; return search(node.children[c-'a'], word, i+1); } } return false;//node.isLeaf; } }
相关推荐
javascript js_leetcode题解之170-two-sum-iii-data-structure-design.js
c c语言_leetcode 0002_add_two_numbers.zip
《LeetCode---C++实现》是一本专注于C++编程语言解决LeetCode在线判题平台上的算法问题的书籍。LeetCode是程序员广泛使用的平台,它提供了大量的编程题目来提升编程技能和算法理解,尤其对于准备面试的程序员来说,...
1. leetCode-126-Word-LadderII.md:这涉及到第126题,词梯问题,通常是一个字符串转换问题,目标是找到两个单词之间的最短转换序列,每次只改变一个字母。 2. leetcode-224-Basic-Calculator.md:这是第224题,基础...
leetcode中国算法和数据结构 算法与数据结构之道 我在这个项目中编写了一些数据结构和算法的 C++ 实现。 你可以阅读关于我的中文体验。 顺便说一下,很多链接可能是中文的。 完毕 选择排序 字符串类 插入排序 我尽力...
java java_leetcode-99-recover-binary-search-tree
python python_leetcode题解之170_Two_Sum_III-Data_structure_design.py
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
Data-Structure-and-Algorithm 所用语言 : Java1.8 编辑器 : IntelliJ Idea 此项目主要用于数据结构的复习以及leetcode算法题目练习。 leetcode算法题解位于leetcode/src 文件夹内,按照题目类型进行区分。 数据...
哈希表 - LeetCode刷题 - 题解
java java_leetcode-105-construct-binary-tree-from-preorder-and-inorde
leetcode 2 Java 中的 LeetCode 解决方案 用 Java 实现的 LeetCode 新颖解决方案的集合。 支持你用最简单的方法从易到难解决问题。 解决方案 LeeCode # 问题 困难 源代码 解决方案 1 中等的 1. 散列 O(n) 和 O(n) ...
LeetCode 101 - A Grinding Guide.pdf
13. Two Sum III Data structure design 两数之和III是一个变体的问题,要求设计一个数据结构来解决两数之和问题。可以使用哈希表或树形结构来解决该问题。 ... 资源摘要信息共包含181个LeetCode题解,涵盖了数组...
c语言入门 c语言_leetcode题解02-add-two-numbers.c
js js_leetcode题解之-add-two-numbers.js
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
c语言入门 c语言_leetcode题解415-add-strings.c
leetcode 接口 该项目可帮助您使用首选的 IDE 或带有命令行界面 (CLI) 的编辑器来执行 leetcode。 入门 先决条件 Windows 10、MacOS、Linux Chrome版 >=90.0.4430 安装 # Prepare your virtual environment conda ...
javascript js_leetcode题解之79-word-search.js