# 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));
            }

            for (int k = curWord.length(); k >= 0; k--) {
                suffix.add(curWord.substring(k));
            }

            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) {
        return map.containsKey(prefix + "#" + suffix) ? map.get(prefix + "#" + suffix) : -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)
