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(m*n) //m – max length of string, n – amount of words
Thys Michels Blog 
Hello Thys!
I am wondering about Space complexity in this assignment.
Since there is basically a prefix map of all possible substrings with all of the words, then space complexity would be O(26*m*n) = O(m,n) , where m — max length of each word, and n – amount of words in total.
Hi kurunve, yes you are correct. Try some of my other challenges and let me know.
List str=new List{‘dog’,’deer’,’deal’};
String s;
s=’de’;
List str2=new List();
for(String ds:str){
if(ds.startsWith(s)){
str2.add(ds);
}
}
System.debug(str2);