Solution: Design Add and Search Words Data Structure

Problem Statement

Design a data structure that supports the addition of new words and the ability to check if a string matches any previously added word.

Implement the Solution class:

Solution() Initializes the object.
void addWord(word) Inserts word into the data structure, making it available for future searches.
bool search(word) Checks if there is any word in the data structure that matches word. The method returns true if such a match exists, otherwise returns false.

Note: In the search query word, the character `'.'

.....

Like the course? Get enrolled and start learning!

E H

· a year ago

I found it a bit more easier and understandable to do this in a BFS way. Time and space complexity remains the same.

// class TrieNode {
//     TrieNode[] children = new TrieNode[26];  // Representing each character of the alphabet.
//     boolean isEnd = false;  // To determine if the current TrieNode marks the end of a word.
// }

public class Solution {
    private TrieNode root;

    public Solution() {
        // ToDo: Write Your Code Here.
        this.root = new TrieNode();
    }

    // Function to add a word into the trie structure.
    public void addWord(String word) {
        // ToDo: Write Your Code Here.
        TrieNode start = root;
        for (char c : word.toCharArray()) {
            if (start.children[c - 'a'] == null) {
                start.children[