# 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 `about``and``apple` Build a prefix tree

It's built like this

### 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