数据结构与算法-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;}
}