> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/facebook/prefix-and-suffix-search.md).

# Prefix and Suffix Search(Trie)

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:

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

分析

1 建2个树，然后pre找pre树，suffix找suffix树，这里倒建倒查。容易超时。

2.insert`'#apple', 'e#apple', 'le#apple', 'ple#apple', 'pple#apple', 'apple#apple'`

into the trie. Then for a query like`prefix = "ap", suffix = "le"`, we can find it by querying our trie for`le#ap`

注意这里weight， 因为w是word的index，所以树里一个Node的w虽然一直被更新，但最新的w就是最后那个word的index,也就是最大的。

```
class WordFilter {



    TrieNode root ;
    public WordFilter(String[] words) {

        root = new TrieNode();

        //建树
        for(int w = 0; w < words.length; w ++){
            String word = words[w] + "{";

            for(int i = 0; i < word.length(); i ++){
                //算起来这里才是每个word开始的地方，所以这里开始初始cur。
                TrieNode cur = root;
                cur.w = w;//每个word得到最新的weight，就是当前的Index.
                for(int j = i; j < 2 * word.length() - 1; j ++){
                    int pos = word.charAt(j % word.length()) - 'a';
                    if(cur.child[pos] == null) {
                        cur.child[pos] = new TrieNode();
                    }
                    cur = cur.child[pos];
                    cur.w = w;
                }
            }
        }

    }

    public int f(String prefix, String suffix) {

        String word = suffix+'{'+prefix;
        TrieNode cur = root;
        int ret = -1;
        for(int i = 0; i < word.length(); i ++){
            int pos = word.charAt(i) - 'a';
            if(cur.child[pos] == null) {
                return -1;
            }
            cur = cur.child[pos];
        }

    return cur.w;
    }

    class TrieNode{
        TrieNode[] child;
        int w;
        TrieNode(){
            this.child = new TrieNode[27];
            this.w = 0;
        }
    }

}

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

.Python

python children里存的是dict\[c] = TrieNode() java是dict\[index]一定要区别清楚

所以这里直接word是 w+#+w 然后遍历整个word， 每个char dict\[char]

```
class TrieNode:
    def __init__(self):
        self.children = dict()
        self.w = 0

class WordFilter:
    def __init__(self, words):
        self.trie = TrieNode()
        for i,w in enumerate(words):
            w = w+"#"+w
            for index in range(len(w)):
                self.appendWord(index,w,i)

    def appendWord(self, i, word, weight):
        cur = self.trie
        for j in word[i:]:
            child = cur.children.get(j)
            if not child:
                child = TrieNode()
                child.w = weight
                cur.children[j] = child
            cur = child

    def f(self, prefix, suffix):
        w = suffix+"#"+prefix
        cur = self.trie
        for c in w:
            if cur: cur = cur.children.get(c)
        return cur.w


obj = WordFilter(["apple", "island","ironman", "i love leetcode"])
param_1 = obj.f("i","d")
print(param_1)
```


---

# 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://nataliekung.gitbook.io/ladder_code/facebook/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.