745-前缀和后缀搜索(Prefix and Suffix Search)
发表于：2021-12-03 | 分类： 困难
字数统计: 363 | 阅读时长: 1分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/prefix-and-suffix-search

英文原文

Design a special dictionary with some words that searchs 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 1:

Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]

Explanation
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.

中文题目

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 WordFilter 类：

  • WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
  • f(string prefix, string suffix) 返回词典中具有前缀 prefix 和后缀suffix 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。

 

示例

输入：
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
输出：
[null, 0]

解释：
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词的 prefix = "a" 且 suffix = 'e" 。

 

提示：

  • 1 <= words.length <= 15000
  • 1 <= words[i].length <= 10
  • 1 <= prefix.length, suffix.length <= 10
  • words[i]、prefix 和 suffix 仅由小写英文字母组成
  • 最多对函数 f 进行 15000 次调用

通过代码

官方题解

方法一：单词查找树 + 集合交集 [超出时间限制]

算法：

  • 我们使用两个单词查找树找出所有前缀匹配的单词和后缀匹配的单词。再通过取集合的交集找到其中权值最大的单词，并返回权重。
  • 然而，集合的元素可能会过大，导致超出时间限制。
[ ]
Trie = lambda: collections.defaultdict(Trie)
WEIGHT = False

class WordFilter(object):
    def __init__(self, words):
        self.trie1 = Trie() #prefix
        self.trie2 = Trie() #suffix
        for weight, word in enumerate(words):
            cur = self.trie1
            self.addw(cur, weight)
            for letter in word:
                cur = cur[letter]
                self.addw(cur, weight)

            cur = self.trie2
            self.addw(cur, weight)
            for letter in word[::-1]:
                cur = cur[letter]
                self.addw(cur, weight)

    def addw(self, node, w):
        if WEIGHT not in node:
            node[WEIGHT] = {w}
        else:
            node[WEIGHT].add(w)

    def f(self, prefix, suffix):
        cur1 = self.trie1
        for letter in prefix:
            if letter not in cur1: return -1
            cur1 = cur1[letter]

        cur2 = self.trie2
        for letter in suffix[::-1]:
            if letter not in cur2: return -1
            cur2 = cur2[letter]

        return max(cur1[WEIGHT] & cur2[WEIGHT])
[ ]
class WordFilter {
    TrieNode trie1, trie2;
    public WordFilter(String[] words) {
        trie1 = new TrieNode();
        trie2 = new TrieNode();
        int wt = 0;
        for (String word: words) {
            char[] ca = word.toCharArray();

            TrieNode cur = trie1;
            cur.weight.add(wt);
            for (char letter: ca) {
                if (cur.children[letter - 'a'] == null)
                    cur.children[letter - 'a'] = new TrieNode();
                cur = cur.children[letter - 'a'];
                cur.weight.add(wt);
            }

            cur = trie2;
            cur.weight.add(wt);
            for (int j = ca.length - 1; j >= 0; --j) {
                char letter = ca[j];
                if (cur.children[letter - 'a'] == null)
                    cur.children[letter - 'a'] = new TrieNode();
                cur = cur.children[letter - 'a'];
                cur.weight.add(wt);
            }
            wt++;
        }
    }

    public int f(String prefix, String suffix) {
        TrieNode cur1 = trie1, cur2 = trie2;
        for (char letter: prefix.toCharArray()) {
            if (cur1.children[letter - 'a'] == null) return -1;
            cur1 = cur1.children[letter - 'a'];
        }
        char[] ca = suffix.toCharArray();
        for (int j = ca.length - 1; j >= 0; --j) {
            char letter = ca[j];
            if (cur2.children[letter - 'a'] == null) return -1;
            cur2 = cur2.children[letter - 'a'];
        }

        int ans = -1;
        for (int w1: cur1.weight)
            if (w1 > ans && cur2.weight.contains(w1))
                ans = w1;

        return ans;
    }
}

class TrieNode {
    TrieNode[] children;
    Set<Integer> weight;
    public TrieNode() {
        children = new TrieNode[26];
        weight = new HashSet();
    }
}

复杂度分析

  • 时间复杂度：$O(NK + Q(N+K))$。其中 $N$ 指的是单词的个数，$K$ 指的是单词中的最大长度，$Q$ 指的是搜索的次数。
  • 空间复杂度：$O(NK)$，单词查找树使用的空间大小。

方法二：成对的单词查找树 [通过]

算法：

  • 假设我们插入了 apple 这个单词。我们可以在单词查找树中插入 ('a', 'e'), ('p', 'l'), ('p', 'p'), ('l', 'p'), ('e', 'a')。然后，如果我们有像 prefix = "ap", suffix = "le" 这样的等长查询，我们可以在单词查找树中找到节点 trie['a'，e']['p'，l']。
  • 如果是不等长的查询呢？例如，要查询 prefix = "app", suffix = "e" 这样的情况，我们可以创建节点 trie['a'，'e']['p'，None]['p'，None]。
  • 在将节点插入单词查找树之后，我们的搜索会很简单。
[ ]
Trie = lambda: collections.defaultdict(Trie)
WEIGHT = False

class WordFilter(object):
    def __init__(self, words):
        self.trie = Trie()

        for weight, word in enumerate(words):
            cur = self.trie
            cur[WEIGHT] = weight
            for i, x in enumerate(word):
                #Put all prefixes and suffixes
                tmp = cur
                for letter in word[i:]:
                    tmp = tmp[letter, None]
                    tmp[WEIGHT] = weight

                tmp = cur
                for letter in word[:-i or None][::-1]:
                    tmp = tmp[None, letter]
                    tmp[WEIGHT] = weight

                #Advance letters
                cur = cur[x, word[~i]]
                cur[WEIGHT] = weight

    def search(self, prefix, suffix):
        cur = self.trie
        for a, b in map(None, prefix, suffix[::-1]):
            if (a, b) not in cur: return -1
            cur = cur[a, b]
        return cur[WEIGHT]
[ ]
class WordFilter {
    TrieNode trie;
    public WordFilter(String[] words) {
        trie = new TrieNode();
        int wt = 0;
        for (String word: words) {
            TrieNode cur = trie;
            cur.weight = wt;
            int L = word.length();
            char[] chars = word.toCharArray();
            for (int i = 0; i < L; ++i) {

                TrieNode tmp = cur;
                for (int j = i; j < L; ++j) {
                    int code = (chars[j] - '`') * 27;
                    if (tmp.children.get(code) == null)
                        tmp.children.put(code, new TrieNode());
                    tmp = tmp.children.get(code);
                    tmp.weight = wt;
                }

                tmp = cur;
                for (int k = L - 1 - i; k >= 0; --k) {
                    int code = (chars[k] - '`');
                    if (tmp.children.get(code) == null)
                        tmp.children.put(code, new TrieNode());
                    tmp = tmp.children.get(code);
                    tmp.weight = wt;
                }

                int code = (chars[i] - '`') * 27 + (chars[L - 1 - i] - '`');
                if (cur.children.get(code) == null)
                    cur.children.put(code, new TrieNode());
                cur = cur.children.get(code);
                cur.weight = wt;

            }
            wt++;
        }
    }

    public int f(String prefix, String suffix) {
        TrieNode cur = trie;
        int i = 0, j = suffix.length() - 1;
        while (i < prefix.length() || j >= 0) {
            char c1 = i < prefix.length() ? prefix.charAt(i) : '`';
            char c2 = j >= 0 ? suffix.charAt(j) : '`';
            int code = (c1 - '`') * 27 + (c2 - '`');
            cur = cur.children.get(code);
            if (cur == null) return -1;
            i++; j--;
        }
        return cur.weight;
    }
}

class TrieNode {
    Map<Integer, TrieNode> children;
    int weight;
    public TrieNode() {
        children = new HashMap();
        weight = 0;
    }
}

复杂度分析

  • 时间复杂度：$O(NK^2 + QK)$。其中 $N$ 指的是单词的个数，$K$ 指的是单词中的最大长度，$Q$ 指的是搜索的次数。
  • 空间复杂度：$O(NK^2)$，单词查找树使用的空间大小。

方法三：后缀修饰的单词查找树 [通过]

算法：

  • 对于 apple 这个单词，我们可以在单词查找树插入每个后缀，后跟 “#” 和单词。
  • 例如，我们将在单词查找树中插入 '#apple', 'e#apple', 'le#apple', 'ple#apple', 'pple#apple', 'apple#apple'。然后对于 prefix = "ap", suffix = "le" 这样的查询，我们可以通过查询单词查找树找到 le#ap。
[ ]
Trie = lambda: collections.defaultdict(Trie)
WEIGHT = False

class WordFilter(object):
    def __init__(self, words):
        self.trie = Trie()

        for weight, word in enumerate(words):
            word += '#'
            for i in xrange(len(word)):
                cur = self.trie
                cur[WEIGHT] = weight
                for j in xrange(i, 2 * len(word) - 1):
                    cur = cur[word[j % len(word)]]
                    cur[WEIGHT] = weight

    def f(self, prefix, suffix):
        cur = self.trie
        for letter in suffix + '#' + prefix:
            if letter not in cur:
                return -1
            cur = cur[letter]
        return cur[WEIGHT]
[ ]
class WordFilter {
    TrieNode trie;
    public WordFilter(String[] words) {
        trie = new TrieNode();
        for (int weight = 0; weight < words.length; ++weight) {
            String word = words[weight] + "{";
            for (int i = 0; i < word.length(); ++i) {
                TrieNode cur = trie;
                cur.weight = weight;
                for (int j = i; j < 2 * word.length() - 1; ++j) {
                    int k = word.charAt(j % word.length()) - 'a';
                    if (cur.children[k] == null)
                        cur.children[k] = new TrieNode();
                    cur = cur.children[k];
                    cur.weight = weight;
                }
            }
        }
    }
    public int f(String prefix, String suffix) {
        TrieNode cur = trie;
        for (char letter: (suffix + '{' + prefix).toCharArray()) {
            if (cur.children[letter - 'a'] == null) return -1;
            cur = cur.children[letter - 'a'];
        }
        return cur.weight;
    }
}

class TrieNode {
    TrieNode[] children;
    int weight;
    public TrieNode() {
        children = new TrieNode[27];
        weight = 0;
    }
}

复杂度分析

  • 时间复杂度：$O(NK^2 + QK)$。其中 $N$ 指的是单词的个数，$K$ 指的是单词中的最大长度，$Q$ 指的是搜索的次数。
  • 空间复杂度：$O(NK^2)$，单词查找树使用的空间大小。

统计信息

通过次数 提交次数 AC比率
3140 7821 40.1%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
添加与搜索单词 - 数据结构设计 中等
字符串 设计 字典树
上一篇:
744-寻找比目标字母大的最小字母(Find Smallest Letter Greater Than Target)
下一篇:
746-使用最小花费爬楼梯(Min Cost Climbing Stairs)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo