数据结构与算法-Trie树添加与搜索
trie树的使用场景
我们若需要制作一个通讯录的软件，使用常规树结构查询的复杂度为O(logn),但trie树的复杂度确与数据多少无关，与单词长度有关，这就大大缩减的查询的时间复杂度。
trie树的基本实现
基础结构
package com.study.trieDemo;
import java.util.TreeMap;
/**
* Created by Zsy on 2020/8/21.
*/
public class Trie {
private class Node {
private boolean isWord;
private 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 int getSize() {
return size;
}
}
添加
/**
* 向tire中添加一个单词
* @param 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树中
* @param word
* @return
*/
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;
}
leetcode中关于trie的题目
208. 实现 Trie (前缀树)
208. 实现 Trie (前缀树)
实现
package com.study.leetcode;
import java.util.TreeMap;
/**
* Created by Zsy on 2020/8/21.
*/
public class Trie_208 {
private Node root;
private class Node {
private boolean isWord;
private TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<Character, Node>();
}
public Node() {
this(false);
}
}
/**
* Initialize your data structure here.
*/
public Trie_208() {
root = new Node();
}
/**
* Inserts a word into the trie.
*/
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;
}
/**
* Returns if the word is in the 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;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(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;
}
}
211. 添加与搜索单词 - 数据结构设计
题目链接
211. 添加与搜索单词 - 数据结构设计
实现
package com.study.leetcode;
import java.util.TreeMap;
/**
* Created by Zsy on 2020/8/21.
*/
public class WordDictionary_211 {
private Node root;
private class Node {
private boolean isWord;
private TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<Character, Node>();
}
public Node() {
this(false);
}
}
/**
* Initialize your data structure here.
*/
public WordDictionary_211() {
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.
*/
/**
* 使用match进行递归查询
* @param word
* @return
*/
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;
}
}
}
677. 键值映射
题目链接
677. 键值映射
题解
package com.study.leetcode;
import java.util.TreeMap;
/**
* Created by Zsy on 2020/8/21.
*/
public class MapSum_677 {
private class Node {
public int value;
public TreeMap<Character, Node> next;
public Node(int value) {
this.value = value;
next = new TreeMap<Character, Node>();
}
public Node() {
this(0);
}
}
private Node root;
/**
* Initialize your data structure here.
*/
public MapSum_677() {
root = new Node();
}
/**
* 非递归法插入节点，通过查询next中是否存在对应key的节点，进行相应插入操作
* @param key
* @param val
*/
public void insert(String key, int val) {
Node cur = root;
for (int i = 0; i < key.length(); i++) {
char c = key.charAt(i);
if (cur.next.get(c) == null)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
cur.value = val;
}
/**
* 找到匹配节点的指针，将地址传给sum进行递归计算
* @param prefix
* @return
*/
public int sum(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 0;
cur = cur.next.get(c);
}
return sum(cur);
}
private int sum(Node node) {
//省略了if(node==null) return 0;
int value = node.value;
for (char c : node.next.keySet()) {
value+=sum(node.next.get(c));
}
return value;
}
}