> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/trie/typeahead.md).

# 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](https://www.lintcode.com/user/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实现方式，仅供一种思路参考。

```java
/**
* 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);
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/trie/typeahead.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.