Leetcode 208. Implement trie (prefix tree) | swiping questions and punching cards

Dust 2021-09-15 10:21:56

Topic link

Prefix tree

Basic concepts

What is a prefix tree ?

Prefix tree (Trie) It's also called dictionary tree , It is a tree data structure , Keys for efficient storage and retrieval of string datasets . This data structure has quite a number of application scenarios , For example, automatic completion and spelling check .

Prefix trees are a little different from ordinary numbers , You need a field to represent , Is it over

Definition of nodes of ordinary tree :

class TreeNode {
val: any;
children: TreeNode[];
}
 Copy code 

Definition of prefix tree node :

class TreeNode {
isEnd: boolean; // Indicates whether the node is the end of a string 
children: { [key: string]: any }; // Children are represented by objects , With the current character as the object key
}
 Copy code 

What does the prefix tree look like ?

Suppose there is 3 A string aboutandapple Build a prefix tree

It's built like this

image-20210909135943745

Ideas

Know the composition of the prefix tree , The code is very clear

  • Insert : Declare a pointer node, Traverse the string to insert , See whether the current character exists in the current node , If it does not exist, create a new node , Then point the pointer to the new node , After traversal , Add an attribute to the last node pointed to by the pointer node.isEnd = ture
  • lookup : Traversing this string , Each character is checked to see if it exists in the prefix tree , There is no direct return false, Exist and traverse to the end isEnd The end of the identification is found , return true
  • Prefix lookup : The process is the same as searching , But is there any isEnd Any logo

Code

class Trie {
children: { [key: string]: any };
constructor() {
this.children = {};
}
/** * Inserts the current string into the prefix tree **/
insert(word: string): void {
let node = this.children;
for (const ch of word) {
if (!node[ch]) {
node[ch] = {}; // If the character doesn't exist , Create a new node 
}
node = node[ch]; // Point to the next character 
}
node.isEnd = true; // Identifies that the current string has ended 
}
/** * Check whether the prefix tree contains the target string as the prefix **/
serachPrefix(word: string): { [key: string]: any } | false {
let node = this.children;
for (const ch of word) {
if (!node[ch]) {
return false; // Cannot find current character , Go straight back to false
}
node = node[ch]; // Point to the next character 
}
return node; // Returns the node corresponding to the last character of the string 
}
/** * Check that the prefix tree contains the target string to find **/
search(word: string): boolean {
const node = this.serachPrefix(word);
return node && !!node.isEnd; // The last node exists and has an end id 
}
/** * Check whether the prefix tree contains the target string as the prefix **/
startsWith(prefix: string): boolean {
return this.serachPrefix(prefix) as boolean; // The last node exists , Whether there is an end sign or not 
}
}
 Copy code 
Please bring the original link to reprint ,thank
Similar articles

2021-09-15

2021-09-15

2021-09-15

2021-09-15