745 Prefix and Suffix Search

745. Prefix and Suffix Search

1. Question

Given manywords,words[i]has weighti.

Design a classWordFilterthat supports one function,WordFilter.f(String prefix, String suffix). It will return the word with givenprefixandsuffixwith 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. wordshas length in range[1, 15000].

2. For each test case, up towords.lengthqueriesWordFilter.fmay be made.

3. words[i]has length in range[1, 10].

4. prefix, suffixhave lengths in range[0, 10].

5. words[i]andprefix, suffixqueries consist of lowercase letters only.

2. Implementation

(1) HashMap

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

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)