Solution Using a Trie

In this problem, we need to implement a contact management system that efficiently handles two operations:

1. Adding a contact to the database.
2. Finding the number of contacts that start with a given prefix.

A naive approach that scans all contacts would be inefficient, particularly with large datasets. Instead, we leverage a Trie (prefix tree) to store and search contacts efficiently, achieving optimal performance.

Approach

We implement a Trie-based solution for fast insertions and prefix lookups:

• TrieNode Structure Each node in the Trie holds:

  • children: A HashMap storing child nodes.

  • words: A counter tracking words passing through the node.

• Trie Operations

  • add(String s): Inserts a word character by character, updating the words count at each step.

  • find(String partial): Traverses the Trie to count how many words share the given prefix.

• Processing Queries The solution efficiently processes "add" and "find" operations using Trie methods.

Complexity Analysis

• Insertion (add) → O(n) where n is the length of the word.
• Search (find) → O(m) where m is the length of the prefix.
• Overall Efficiency → Much faster than brute-force approaches.

Java:

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    int words = 0;
}

class Trie {
    private final TrieNode root = new TrieNode();

    public void add(String s) {
        TrieNode node = root;
        for (char ch : s.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
            node.words++;
        }
    }

    public int find(String partial) {
        TrieNode node = root;
        for (char ch : partial.toCharArray()) {
            if (!node.children.containsKey(ch)) return 0;
            node = node.children.get(ch);
        }
        return node.words;
    }
}

class Result {
    public static List<Integer> contacts(List<List<String>> queries) {
        List<Integer> result = new ArrayList<>();
        Trie trie = new Trie();
        for (List<String> query : queries) {
            if (query.get(0).equals("add")) {
                trie.add(query.get(1));
            } else {
                result.add(trie.find(query.get(1)));
            }
        }
        return result;
    }
}