代码拉取完成,页面将自动刷新
package code;
/*
* 208. Implement Trie (Prefix Tree)
* 题意:字典树
* 难度:Medium
* 分类:Design, Trie
* 思路:字典树是一个数据结构,这个数据结构里包含很多TrieNode,每个TireNode都用一个长度为26的TrieNode[]数组表示该字符的下一个字符对象
* Tips:
*/
public class lc208 {
class TrieNode {
public char val;
public boolean isWord;
public TrieNode[] children = new TrieNode[26];
public TrieNode() {}
TrieNode(char c){
TrieNode node = new TrieNode();
node.val = c;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
root.val = ' ';
}
public void insert(String word) {
TrieNode ws = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(ws.children[c - 'a'] == null){
ws.children[c - 'a'] = new TrieNode(c);
}
ws = ws.children[c - 'a'];
}
ws.isWord = true;
}
public boolean search(String word) {
TrieNode ws = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(ws.children[c - 'a'] == null) return false;
ws = ws.children[c - 'a'];
}
return ws.isWord;
}
public boolean startsWith(String prefix) {
TrieNode ws = root;
for(int i = 0; i < prefix.length(); i++){
char c = prefix.charAt(i);
if(ws.children[c - 'a'] == null) return false;
ws = ws.children[c - 'a'];
}
return true;
}
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。