Implement typeahead. Given a string and a dictionary, return all words that contains the string as a substring. The dictionary will give at the initialize method and wont be changed. The method to find all words with given substring would be called multiple times.


Given dictionary ={"Jason Zhang", "James Yu", "Bob Zhang", "Larry Shi"}

search"Zhang", return["Jason Zhang", "Bob Zhang"].

search"James", return["James Yu"].



  • 在client进行search之前就把所有的可能性都枚举出来。build up inverted index

  • 通过一个Map来实现cache的效果,使得访问过的typeahead直接存储在Map中,因为Hash的速度是很快的,所以再次访问时直接从Hash中取出即可。

所谓的优化的核心都在于用空间换时间 Notice, when building up inverted index, you need to make sure no duplicated insert. For example, for different words, you may insert the same word for same substring multiple times

有点奇怪的问题,没有用到Trie,而是用了Inverted Index。


LintCode Official


* This reference program is provided by @jiuzhang.com
* Copyright is reserved. Please indicate the source for forwarding

public class Typeahead {
    private HashMap<String, List<String>> map = new HashMap<String , List<String>>();
    // @param dict A dictionary of words dict
    public Typeahead(Set<String> dict) {
        // do initialize if necessary
        for (String str : dict) {
            int len = str.length();
            for (int i = 0; i < len; ++i)
                for (int j = i + 1; j <= len; ++j) {
                    String tmp = str.substring(i, j);
                    if (!map.containsKey(tmp)) {
                        map.put(tmp, new ArrayList<String>());
                    } else {
                        List<String> index = map.get(tmp);
                        if (!str.equals(index.get(index.size() - 1))) {

    // @param str: a string
    // @return a list of words
    public List<String> search(String str) {
        // Write your code here
        if (!map.containsKey(str)) {
            return new ArrayList<String>();
        } else {
            return map.get(str);

Last updated