Typeahead

Description

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.

Example

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

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

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

Analysis

@panda111

• 在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。

Solution

LintCode Official

注意：这个方法没有用Trie，不能算成标准的Typeahead实现方式，仅供一种思路参考。

/**
* 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>());
                        map.get(tmp).add(str);
                    } else {
                        List<String> index = map.get(tmp);
                        if (!str.equals(index.get(index.size() - 1))) {
                            index.add(str);
                        }
                    }
                }
        }
    }

    // @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);
        }
    }
}