Add and Search Word - Data structure design
2024-10-18 11:13:47
https://leetcode.com/problems/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.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
解题思路：
这题实际上是 Implement Trie (Prefix Tree) 的follow-up。有了上一题的设计，这题唯一需要解决的，就是search这个方法，当遇到'.'的时候，如何办。
本题的addword()方法中，是没有'.'的，所以Trie树内肯定没有'.'。那么当遇到'.'的时候，只要递归search下一层次的所有子节点，有一个路径里找到，就返回true，否则立刻返回false。
public class WordDictionary {
class TrieNode {
// Initialize your data structure here.
boolean isWord;
Map<Character, TrieNode> next;
public TrieNode() {
next = new HashMap<Character, TrieNode>();
isWord = false;
}
}
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
// Adds a word into the data structure.
public void addWord(String word) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i++) {
if(cur.next.get(word.charAt(i)) == null) {
TrieNode next = new TrieNode();
cur.next.put(word.charAt(i), next);
}
cur = cur.next.get(word.charAt(i));
}
cur.isWord = 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 searchHelper(root, word);
}
public boolean searchHelper(TrieNode cur, String word) {
if(cur == null) {
return false;
}
for(int i = 0; i < word.length(); i++) {
if(word.charAt(i) != '.') {
cur = cur.next.get(word.charAt(i));
} else {
for(TrieNode value : cur.next.values()) {
if(searchHelper(value, word.substring(i + 1))) {
return true;
}
}
return false;
}
if(cur == null) {
return false;
}
}
return cur.isWord;
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
2018/6/20 二刷
class TrieNode {
HashMap<Character, TrieNode> node;
boolean isWord;
public TrieNode() {
node = new HashMap<Character, TrieNode>();
isWord = false;
}
}
public class WordDictionary {
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
if (!cur.node.containsKey(word.charAt(i))) {
TrieNode node = new TrieNode();
cur.node.put(word.charAt(i), node);
}
cur = cur.node.get(word.charAt(i));
}
cur.isWord = 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 searchHelper(root, word);
}
public boolean searchHelper(TrieNode cur, String word) {
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) == '.') {
// 这里是所有都没找到才返回false，不能直接return searchHelper(cur.node.get(key), word.substring(i + 1))
for (Character key : cur.node.keySet()) {
if (searchHelper(cur.node.get(key), word.substring(i + 1))) {
return true;
}
}
return false;
}
if (!cur.node.containsKey(word.charAt(i))) {
return false;
}
cur = cur.node.get(word.charAt(i));
}
return cur.isWord;
}
private TrieNode root;
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
最新文章
- svn上传工程之后下载，打开下载之后的工程缺少文件
- linux中的内存申请函数的区别 kmalloc, vmalloc
- Android Programing 学习笔记（一）
- mongoose学习笔记3--简单查询1
- nginx爆出新漏洞 最低限度可造成DDos攻击
- VMware系统运维（二十）部署虚拟化桌面Horzion View 5.2 HTML Access进行连接测试
- PKM（personal knowledge management）
- 分布式配置管理平台 Disconf
- 读书笔记：javascript高级程序设计
- Fun<>，匿名方法，Lambda表达式 冒泡排序C#
- CSS3线性渐变
- UVa 496 - Simply Subsets
- Swift 2.2 最基本的多线程
- 数据管理 - 每天5分钟玩转 Docker 容器技术（147）
- ASP.NET Core 与支付宝开发文档
- day2 网络基础
- Confluence 6 编辑站点欢迎消息
- 【6集iCore3_ADP触摸屏驱动讲解视频】6-3 底层驱动之液晶显示
- [LeetCode] 849. Maximize Distance to Closest Person_Easy tag: BFS
- 公钥与私钥，HTTPS详解 转载