We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trie
  4. Contacts
  5. Discussions

Contacts

Sort by

recency

|

335 Discussions

|

  • abner_magalhaes
     + 0 comments

    My best C++ solution using Unordered_map. It may not be safe and I think I'm breaking some rules, but it was the closest I could get. It passed all tests.

    .

    vector<int> contacts(vector<vector<string>> queries) {
    
    vector<int> results;
    unordered_map<string, int> chars;
    
    for(vector<string>& query : queries) {
        
        string& cmd      = query[0];    
        string& cmdValue = query[1];
        
        if(cmd == "add") {
            
            string name = "";
            for(char& c : cmdValue) {
                name.push_back(c);
                chars[name]++;
            }
            
            continue;
            
        }
        
        results.push_back(chars[cmdValue]);        
        
    }
    
    return results;
}

  • Anophoo
     + 0 comments

    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;
    }
}

  • ludovic_tirtiaux
     + 0 comments

    C# solution using a tree where each node has potentially 26 children.

    class Result
{     
    class Node
    {
        public int Count = 0;
        public Node[] Children = new Node[26];        
    }

    public static List<int> contacts(List<List<string>> queries)
    {
        List<int> counts = new List<int>();
        Node root = new Node();
        
        foreach (List<string> q in queries)
        {
            if (q[0] == "add")
            {
                Node currentNode = root;
                foreach (char c in q[1])
                {
                    if (currentNode.Children[c - 'a'] == null)
                    {
                        Node n = new Node();
                        n.Count = 1;
                        currentNode.Children[c - 'a'] = n;                        
                    }
                    else 
                    {
                        currentNode.Children[c - 'a'].Count++;
                    }
                    currentNode = currentNode.Children[c - 'a'];
                }
            }
            else if (q[0] == "find")
            {
               
                Node currentNode = root;
                int count = 0;
                int depth = 1;
                foreach (char c in q[1])
                {                    
                    if (currentNode.Children[c - 'a'] == null)
                        break;                 
                    if (q[1].Length == depth)
                        count = currentNode.Children[c - 'a'].Count;
                    depth++;     
                    
                    currentNode = currentNode.Children[c - 'a'];               
                }
                                
                counts.Add(count);
            }                
        }

        return counts;
}

    }

  • css_rique
     + 0 comments

    This is my solution for Python 3.5+ using dictionaries.

    def contacts(queries):
    arr = defaultdict(list)
    r = []
    
    def find(word):
        index = word[0]
        l = len(word)
        r = 0
        
        for v in arr[index]:
            if v[:l] == word:
                r +=1
        return r
        
    for q in queries:
        op, v = q
        
        if op == 'add':
            arr[v[0]].append(v)
        elif op == 'find':
            r.append(find(v))
    return r

  • Shoveet21
     + 0 comments

    Simple java code using Trie -

    class TrieNode{ TrieNode[] children = new TrieNode[26]; int we,prefix; public TrieNode(){ we=0; prefix=0; for(int i=0;i<26;i++) children[i]=null; } }

    class Result {

        public static TrieNode root = new TrieNode();
    static int c=0;

    public static void Insert(String s){
       TrieNode copy=root;
       for(int i=0;i<s.length();i++){
               int ch=s.charAt(i)-'a';
               if(copy.children[ch]==null)
               copy.children[ch]=new TrieNode();
               copy=copy.children[ch];
               copy.prefix++;
       }
       copy.we++;
       return;
    }

    public static int Search(String s){
            TrieNode copy=root;
            for(int i=0;i<s.length();i++){
                    int ch=s.charAt(i)-'a';
                    if(copy.children[ch]==null)
                    return 0;
                     copy=copy.children[ch];
            }
            c=copy.prefix;
            return c;
    }

public static List<Integer> contacts(List<List<String>> queries) {
// Write your code here
List<Integer> l=new ArrayList<Integer>();
for(List<String> i: queries){
if(i.get(0).equals("add"))
Insert(i.get(1));
else{
        c=0;
int count = Search(i.get(1));
l.add(count);
}
}
return l;

    } }