876601. Design Add and Search Words Data Structure
Design Add and Search Words Data Structure
Summary
The problem is about designing a data structure that allows you to add words and search for words in an efficient manner. The key concept involved is Trie (prefix tree) data structure, which is commonly used in string manipulation problems.
Detailed Explanation
To design the "Add and Search Words Data Structure", we can use a Trie data structure. A Trie is a tree-like data structure where each node represents a prefix of some word in the dictionary. This allows us to efficiently add and search words in the dictionary.
Here's how it works:
- Initialize an empty Trie.
- When adding a new word, traverse the Trie using the characters in the word. If a character is not found in the current node, create a new node with that character as its prefix.
- Continue traversing until you reach the end of the word (i.e., all characters have been processed).
- To search for a word, start at the root of the Trie and traverse down using each character in the word. If the entire word is found, return true; otherwise, return false.
Here's an ASCII art representation of the Trie:
+---+
| |
+---+
/ \
/ \
T E
/ \ / \
R I S T
/ \ / \
A C A T
| | | | |
M O N O
Time Complexity: The time complexity of adding a word is O(k), where k is the length of the word. Searching for a word also takes O(k) time.
Space Complexity: The space complexity is O(N), where N is the total number of characters in all words, since each node in the Trie can have at most 26 children (for lowercase English letters).
Optimized Solutions
Java
class TrieNode {
boolean isEndOfWord;
TrieNode[] children = new TrieNode[26];
public TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; i++) {
children[i] = null;
}
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void add(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
if (current.children[ch - 'a'] == null) {
current.children[ch - 'a'] = new TrieNode();
}
current = current.children[ch - 'a'];
}
current.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
if (current.children[ch - 'a'] == null) {
return false;
}
current = current.children[ch - 'a'];
}
return current.isEndOfWord;
}
}