Because love so insist, because love so wait. Through the long days without drama to play, finally for the spring of life, mutual encouragement!!
Dictionary trees, also known as prefix trees or Trie trees, are common data structures for handling strings. Trie is often used by search engine systems. It has the advantage of reducing query time and minimizing unnecessary string comparisons by using a common prefix for strings.
Assuming that the characters that make up all the words are only “A” to “Z”, please implement a dictionary tree structure with the following four main functions:
Void insert(String word) : Adds word, which can be added repeatedly. Void delete(String word) : deletes word. If word has been added multiple times, delete word only once. Int search(String word) : Returns the number of words in the dictionary tree. Int serachPrefix(String pre) : Returns the number of words prefixed with the String pre.
The implementation code is as follows:
packageTree;class TrieNode {
public int pass;
public int end;
public TrieNode[] nexts;
public TrieNode(a) {
//pass indicates the number of times the string containing this character is passed
pass = 0;
//end indicates the number of strings ending with this character
end = 0;
// Indicates 26 letters
nexts = new TrieNode[26]; }}public class Trie {
private TrieNode root;
public Trie(a) {
root = new TrieNode();
}
public void insert(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
TrieNode node = root;
node.pass++; // The number of passes +1
int index = 0;
for (int i = 0; i < chs.length; i++) { // iterate over characters from left to right
index = chs[i] - 'a';
// If not, create a new path
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
// Others go to the sub-path
node = node.nexts[index];
node.pass++;
}
node.end++;// The number of strings ending with this character +1
}
public int search(String word) {
if (word == null) {
return 0;
}
TrieNode node = root;
char[] chs = word.toCharArray();
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) { // The string was not inserted if the subpath is not changed
return 0;
}
node = node.nexts[index];
}
return node.end; // Returns the number of strings ending in this word
}
public int searchPrefix(String pre) {
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
if (node.nexts[index] == null) { // The string was not inserted if the subpath is not changed
return 0;
}
node = node.nexts[index];
}
return node.pass; // Returns the number of strings prefixed with that string
}
public void delete(String word) {
int flag = search(word); / / to find first
if (flag == 0) {
return;
}
char[] chs = word.toCharArray();
TrieNode node = root;
node.pass--; // Start at the root -1
int index = 0;
for (int i = 0; i < chs.length; i++) { // iterate over characters from left to right
index = chs[i] - 'a';
if (--node.nexts[index].pass == 0) { // If --pass == 0, node.nexts[index] is set to null, and GC will automatically reclaim the clipped path
node.nexts[index] = null;
return;
}
node.pass--; // Quantity minus onenode = node.nexts[index]; } node.end--; Number of strings already terminated by this character minus one}}Copy the codeThe insert
To {” ABC “, “abcd”, “abce”, “BCD”, “BCF”, “cde}”, for example, insert all string after the results are as follows:
We know from the pass value of the root node that six strings have been inserted
Delete operation
After abcd is deleted:
Query operation
Take the query “ABC” as an example
Returns 1, the “ABC” string exists and the number is 1
Prefix query operation
Take the query “ab” as an example
Return pass==2, indicating that there are two strings prefixed with ab
LeetCode examples:677. Key-value mapping
Implement a MapSum class with two methods, insert and sum:
Void Insert (String key, int val) Inserts key-value pairs. The String represents the key and the integer represents the value val. If the key already exists, the original key-value pair is replaced by the new key-value pair. Int sum(string prefix) Returns the sum of all key values starting with prefix.
Example:
Input: [” MapSum “, “insert”, “sum”, “insert”, “sum”] [[], [” apple “, 3], [” ap “], [” app “, 2], [” ap “]] output: [null, null, 3, null, 5]
MapSum = new MapSum(); mapSum.insert(“apple”, 3); mapSum.sum(“ap”); // return 3 (apple = 3) mapSum.insert(“app”, 2); mapSum.sum(“ap”); // return 5 (apple + app = 3 + 2 = 5)
Tip:
1 <= key.length, prefix. Length <= 50 Key and prefix consist of lowercase letters only. 1 <= val <= 1000 Insert and sum can be called a maximum of 50 times
Use prefix tree to save character paths
Recursive solution:
class MapSum {
public MapSum(a) {}private class Node {
Node[] nexts = new Node[26];
int value;
}
private Node root = new Node();
public void insert(String key, int val) {
insert(key, root, val);
}
public void insert(String key,Node node, int val) {
if (key == null) {
return;
}
if (key.length() == 0) {
node.value = val;
return;
}
int index = key.charAt(0) - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new Node();
}
node = node.nexts[index];
insert(key.substring(1),node,val);
}
public int sum(String prefix) {
return sum(prefix,root);
}
public int sum(String prefix,Node node) {
if (node == null) return 0;
if (prefix == null) return 0;
if(prefix.length() ! =0) {
int index = prefix.charAt(0) - 'a';
node = node.nexts[index];
return sum(prefix.substring(1),node);
}
int sumAll = node.value;
for (Node n : node.nexts) {
sumAll += sum(prefix,n);
}
returnsumAll; }}Copy the codeIterative solution:
class MapSum {
public MapSum(a) {}private class TrieNode {
TrieNode[] nexts = new TrieNode[26];
int value;
}
TrieNode root = new TrieNode();
Queue<TrieNode> queue = new LinkedList<>();
public void insert(String key, int val) {
if (key == null) {
return;
}
char[] chs = key.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
}
node.sum = val;
}
public int sum(String prefix) {
if (prefix == null) {
return 0;
}
TrieNode node = root;
int index = 0;
char[] chs = prefix.toCharArray();
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
int sumAll = node.sum;
queue.add(node);
while(! queue.isEmpty()) { TrieNode[] next = queue.remove().nexts;for (int i = 0; i <26; i++) {if(next[i] ! =null) { sumAll += next[i].sum; queue.add(next[i]); }}}returnsumAll; }}Copy the code
