[Leetcode] Problem 745 - Prefix and Suffix Search

Posted on | In ,

Design a special dictionary which has some words and allows you to search the words in it by a prefix and a suffix.

Implement the WordFilter class:

  • WordFilter(string[] words) Initializes the object with the words in the dictionary.
  • f(string prefix, string suffix) Returns the index of the word in the dictionary which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

Example

Input
[“WordFilter”, “f”]
[[[“apple”]], [“a”, “e”]]

Output
[null, 0]

Explanation

1
2
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = 'e".

Constraints

  • 1 <= words.length <= 15000
  • 1 <= words[i].length <= 10
  • 1 <= prefix.length, suffix.length <= 10
  • words[i], prefix and suffix consist of lower-case English letters only.
  • At most 15000 calls will be made to the function f.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class TrieNode {
    private int index = -1;
    private TrieNode[] children = new TrieNode[27];
}

public class TrieTree {
    private TrieNode root;

    public TrieTree(TrieNode root) {
        this.root = root;
    }

    public void insert(String word, int index) {
        TrieNode node = root;

        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';

            if (node.children[idx] == null)
                node.children[idx] = new TrieNode();

            node = node.children[idx];
            node.index = index;
        }
    }

    public int startsWith(String prefix) {
        TrieNode node = find(prefix);
        return node == null ? -1 : node.index;
    }

    private TrieNode find(String prefix) {
        TrieNode node = root;

        for (int i = 0; i < prefix.length(); i++) {
            int idx = prefix.charAt(i) - 'a';

            if (node.children[idx] == null)
                return null;

            node = node.children[idx];
        }

        return node;
    }
}

private TrieTree tree;

public WordFilter(String[] words) {
    tree = new TrieTree(new TrieNode());

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

        for (int i = 0; i < word.length(); i++)
            tree.insert(word.substring(i) + "{" + word, idx);
    }
}

public int f(String prefix, String suffix) {
    return tree.startsWith(suffix + "{" + prefix);
}