首页 / JAVA / java 自习室 day 24
java 自习室 day 24
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java 自习室 day 24,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2304字,纯文字阅读大概需要4分钟。
内容图文
leetcode 211题
题目
设计一个支持以下两种操作的数据结构:
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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-and-search-word-data-structure-design
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
字典树
题目所需的数据结构是一种字典树,每颗树节点可以拥有任意边,用一个数组来表示,节点上存放布尔值,标志当前节点是否是叶子节点
本题中需要存储所有英文字母26个,因此字典树设计如下:
class TrieNode {
public TrieNode[] next;
public boolean is_end;
public TrieNode() {
//共26个字母
next = new TrieNode[26];
is_end = false;
}
}
WordDictionary
添加操作
每次从root节点出发,在数组相应位置添加字符
用字符的ASCII码来对应其在数组中的下标,可以以O(1)的时间复杂度完成查找
查找操作
当遇到’.'的时候,此时需要遍历全部26条边,任意一条边存在就需要往下继续遍历
public class WordDictionary {
public TrieNode root;
/**
* Initialize your data structure here.
*/
public WordDictionary() {
root = new TrieNode();
}
/**
* Adds a word into the data structure.
*/
public void addWord(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char s = word.charAt(i);
if (node.next[s - 'a'] == null) {
node.next[s - 'a'] = new TrieNode();
}
node = node.next[s - 'a'];
}
node.is_end = 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);
}
public boolean search(TrieNode node, String word, int i) {
if (i >= word.length()) {
return node.is_end;
}
//进行深度搜索
char s = word.charAt(i);
if (s == '.') {
for (int j = 0; j < 26; j++) {
if (node.next[j] != null && search(node.next[j], word, i + 1)) {
return true;
}
}
return false;
} else {
if (node.next[s - 'a'] != null && search(node.next[s - 'a'], word, i + 1)) {
return true;
}
return false;
}
}
}
测试
public static void main(String[] args) {
String a = "bad";
String b = "mad";
String c = "dad";
WordDictionary wd = new WordDictionary();
wd.addWord(a);
wd.addWord(b);
wd.addWord(c);
wd.search("pad");
wd.search("bad");
wd.search(".ad");
wd.search("b..");
}
内容总结
以上是互联网集市为您收集整理的java 自习室 day 24全部内容,希望文章能够帮你解决java 自习室 day 24所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。