# 745     Prefix and Suffix Search

## 745. [Prefix and Suffix Search](https://leetcode.com/problems/prefix-and-suffix-search/description/)

## 1. Question

Given many`words`,`words[i]`has weight`i`.

Design a class`WordFilter`that supports one function,`WordFilter.f(String prefix, String suffix)`. It will return the word with given`prefix`and`suffix`with maximum weight. If no word exists, return -1.

**Examples:**

```
Input:

WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1
```

**Note:**

1. `words`has length in range`[1, 15000]`.
2. For each test case, up to`words.length`queries`WordFilter.f`may be made.
3. `words[i]`has length in range`[1, 10]`.
4. `prefix, suffix`have lengths in range`[0, 10]`.
5. `words[i]`and`prefix, suffix`queries consist of lowercase letters only.

## 2. Implementation

(1) HashMap

```java
class WordFilter {
    Map<String, Integer> map;

    public WordFilter(String[] words) {
        map = new HashMap();


        for (int i = 0; i < words.length; i++) {
            String curWord = words[i];

            List<String> prefix = new ArrayList();
            List<String> suffix = new ArrayList();

            for (int j = 0; j <= curWord.length(); j++) {
                prefix.add(curWord.substring(0, j));
                suffix.add(curWord.substring(j));
            }

            for (String p : prefix) {
                for (String s : suffix) {
                    String key = p + "#" + s;

                    if (!map.containsKey(key)) {
                        map.put(key, i);
                    }
                    else {
                        map.put(key, Math.max(map.get(key),i));
                    }
                }
            }
        }
    }

    public int f(String prefix, String suffix) {
        String key = prefix + "#" + suffix;
        return map.containsKey(key) ? map.get(key) : -1;
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */
```

(2) Trie

思路: 利用trie的特性，将suffix + "#" + prefix作为key插入trie里，并以此作为查询的key

```java
class WordFilter {
    class TrieNode {
        int weight;
        boolean isWord;
        TrieNode[] childNode;

        public TrieNode() {
            weight = -1;
            childNode = new TrieNode[256];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word, int weight) {
            if (word == null || word.length() == 0) {
                return;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int index = c;
                if (curNode.childNode[index] == null) {
                    curNode.childNode[index] = new TrieNode();
                }
                curNode = curNode.childNode[index];
                curNode.weight = weight;
            }
            curNode.isWord = true;
        }

        public TrieNode search(String word) {
            if (word == null || word.length() == 0) {
                return null;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int index = c;
                if (curNode.childNode[index] == null) {
                    return null;
                }
                curNode = curNode.childNode[index];
            }
            return curNode;
        }

        public int getWeight(String word) {
            TrieNode node = search(word);
            return node == null ? -1 : node.weight;
        }
    }

    Trie trie;
    public WordFilter(String[] words) {
        trie = new Trie();

        for (int i = 0; i < words.length; i++) {
            String curWord = words[i];
            String key = "#" + curWord;
            trie.insert(key, i);

            for (int j = curWord.length() - 1; j >= 0; j--) {
                key = curWord.charAt(j) + key;
                trie.insert(key, i);
            }
        }
    }

    public int f(String prefix, String suffix) {
        return trie.getWeight(suffix + "#" + prefix);
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */
```

## 3. Time & Space Complexity

HashMap: 时间复杂度O(nl^2), n是word的个数, l是word的平均长度, 空间复杂度O(nl^2)

Trie: 时间复杂度O(nl^2), n是word的个数, l是word的平均长度, 空间复杂度O(nl^2)


---

# Agent Instructions: 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://protegejj.gitbook.io/oj-practices/chapter1/trie/745-prefix-and-suffix-search.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.