目录
-
什么是字典树
-
基于TreeMap的字典树
package com.suanfa.trie;
import java.util.TreeMap;
/**
* 字典树（存储单词）基于TreeMap
* @author Administrator
*
*/
public class Trie {
private class Node{
public boolean isWord;//是否是一个单词
public TreeMap<Character, Node> next;//存储字母
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<Character, Node>();
}
public Node(){
this(false);
}
}
private Node root;//根节点
private int size;
public Trie(){
root = new Node();
size = 0;
}
// 获得Trie中存储的单词数量
public int getSize(){
return size;
}
// 向Trie中添加一个新的单词word
public void add(String word){
Node cur = root;//从根节点开始添加
for(int i = 0 ; i < word.length() ; i ++){
char c = word.charAt(i);//获取单词中的每一个字母
if(cur.next.get(c) == null)//当前节点的下一个节点中没有存储这个字母，添加进去
cur.next.put(c, new Node());
cur = cur.next.get(c);//否则向下寻找
}
//如果不是一个单词则为空格，单词数加一
if(!cur.isWord){
cur.isWord = true;
size ++;
}
}
// 查询单词word是否在Trie中
public boolean contains(String word){
//从根节点开始遍历
Node cur = root;
for(int i = 0 ; i < word.length() ; i ++){
char c = word.charAt(i);
if(cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return cur.isWord;
}
// 查询是否在Trie中有单词以prefix为前缀
public boolean isPrefix(String prefix){
Node cur = root;
for(int i = 0 ; i < prefix.length() ; i ++){
char c = prefix.charAt(i);
if(cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return true;
}
}
-
不使用map实现字典树
package com.suanfa.trie;
/**
* 字典树，不用map
* @author Administrator
*
*/
public class Trie3 {
private class Node{
public boolean isWord;
public Node[] next;
public Node(boolean isWord){
this.isWord = isWord;
next = new Node[26];
}
public Node(){
this(false);
}
}
private Node root;
private int size;
public Trie3(){
root = new Node();
size = 0;
}
// 获得Trie中存储的单词数量
public int getSize(){
return size;
}
// 向Trie中添加一个新的单词word
public void add(String word){
Node cur = root;
for(int i = 0 ; i < word.length() ; i ++){
char c = word.charAt(i);
if(cur.next[c-'a'] == null)
cur.next[c-'a'] = new Node();
cur = cur.next[c-'a'];
}
if(!cur.isWord){
cur.isWord = true;
size ++;
}
}
// 查询单词word是否在Trie中
public boolean contains(String word){
Node cur = root;
for(int i = 0 ; i < word.length() ; i ++){
char c = word.charAt(i);
if(cur.next[c-'a'] == null)
return false;
cur = cur.next[c-'a'];
}
return cur.isWord;
}
}
-
例题208实现一个前缀树
package com.suanfa.trie;
/// 208. Implement Trie (Prefix Tree)
/// https://leetcode.com/problems/implement-trie-prefix-tree/description/
import java.util.TreeMap;
/**
* 实现一个前缀树
* @author Administrator
*
*/
public class Trie208 {
private class Node{
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<Character, Node>();
}
public Node(){
this(false);
}
}
private Node root;
public Trie208(){
root = new Node();
}
// 向Trie中添加一个新的单词word
public void insert(String word){
Node cur = root;
for(int i = 0 ; i < word.length() ; i ++){
char c = word.charAt(i);
if(cur.next.get(c) == null)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
cur.isWord = true;
}
// 查询单词word是否在Trie中
public boolean search(String word){
Node cur = root;
for(int i = 0 ; i < word.length() ; i ++){
char c = word.charAt(i);
if(cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return cur.isWord;
}
// 查询是否在Trie中有单词以prefix为前缀
public boolean startsWith(String isPrefix){
Node cur = root;
for(int i = 0 ; i < isPrefix.length() ; i ++){
char c = isPrefix.charAt(i);
if(cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return true;
}
}
-
练习211添加和搜索单词
package com.suanfa.trie;
/// Leetcode 211. Add and Search Word - Data structure design
/// https://leetcode.com/problems/add-and-search-word-data-structure-design/description/
import java.util.TreeMap;
/**
* 添加和搜索单词
* @author Administrator
*
*/
public class WordDictionary {
private class Node{
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<Character, Node>();
}
public Node(){
this(false);
}
}
private Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node();
}
/**添加单词 Adds a word into the data structure. */
public void addWord(String word) {
Node cur = root;
for(int i = 0 ; i < word.length() ; i ++){
char c = word.charAt(i);
if(cur.next.get(c) == null)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
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 match(root, word, 0);
}
private boolean match(Node node, String word, int index){
if(index == word.length())
return node.isWord;
char c = word.charAt(index);
if(c != '.'){
if(node.next.get(c) == null)
return false;
return match(node.next.get(c), word, index + 1);
}
else{
for(char nextChar: node.next.keySet())
if(match(node.next.get(nextChar), word, index + 1))
return true;
return false;
}
}
}
京公网安备 11010502036488号