Tap here to switch tabs
Problem
Submissions

Problem: Implement Trie

Implement Trie (Prefix Tree) by storing words and supporting insertion, complete-word searches, and prefix searches. Return whether each requested word or prefix exists.

Statement

Trie is a tree-like data structure used to store strings. The tries are also called prefix trees because they provide very efficient prefix-matching operations. Implement a trie data structure with three functions that perform the following tasks:

  • Insert (word): This inserts a word into the trie.

  • Search (word): This searches the given word in the trie and returns TRUE if the complete word is found (i.e., all characters match and the last node is marked as the end of a word). Otherwise, return FALSE.

  • Search prefix (prefix): This searches the given prefix in the trie and returns TRUE if the prefix path exists in the trie (i.e., all prefix characters match), regardless of whether the last node is marked as the end of a word. Otherwise, return FALSE.

Constraints:

  • 1≤1 \leq word.length, prefix.length ≤500\leq 500

  • The strings consist only of lowercase English letters.

  • At most, 10310^3 calls in total will be made to the functions.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Implement Trie

Implement Trie (Prefix Tree) by storing words and supporting insertion, complete-word searches, and prefix searches. Return whether each requested word or prefix exists.

Statement

Trie is a tree-like data structure used to store strings. The tries are also called prefix trees because they provide very efficient prefix-matching operations. Implement a trie data structure with three functions that perform the following tasks:

  • Insert (word): This inserts a word into the trie.

  • Search (word): This searches the given word in the trie and returns TRUE if the complete word is found (i.e., all characters match and the last node is marked as the end of a word). Otherwise, return FALSE.

  • Search prefix (prefix): This searches the given prefix in the trie and returns TRUE if the prefix path exists in the trie (i.e., all prefix characters match), regardless of whether the last node is marked as the end of a word. Otherwise, return FALSE.

Constraints:

  • 1≤1 \leq word.length, prefix.length ≤500\leq 500

  • The strings consist only of lowercase English letters.

  • At most, 10310^3 calls in total will be made to the functions.