Apex Coding Interview Challenge #8

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

Solution

public Map<String, List<String>> mapOfDictionary(List<String> wordsLst){
    Map<String, List<String>> dictionaryMap = new Map<String, List<String>>();
    
    for (String w : wordsLst){
        List<String> wordChars = new List<String>(w.split(''));
        String concatChars = '';
        for (String wordChar : wordChars){
            concatChars += wordChar;
            if (dictionaryMap.containsKey(concatChars)){
                List<String> wordsForChars = dictionaryMap.get(concatChars);
                wordsForChars.add(w);
                dictionaryMap.put(concatChars, wordsForChars);
            } else {
                dictionaryMap.put(concatChars, new List<String>{w});
            }
        }   
    }
   
    return dictionaryMap;
}

public List<String> getWordsForAutoComplete(String word){
    Map<String, List<String>> dictionaryMap = mapOfDictionary(new List<String>{'dog', 'deer', 'deal'});
    return dictionaryMap.get(word);
}

Testing

System.debug(getWordsForAutoComplete('de')); //(deer, deal)

Complexity Analysis
Time complexity: O(n^2)
Space complexity: O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: