Python中使用给定的前缀和后缀在字典中搜索字符串

在本教程中，我们将编写 Python 程序来搜索字典中具有给定前缀和后缀的字符串。我们给出一个数组，由 N 个字符串和 Q 个查询组成，形式为两个字符串前缀和后缀。我们的任务是获取给定数组中具有给定前缀和后缀的任何字符串。

输入：
arr = ["apple", "app", "biscuit", "mouse", "orange", "bat", "microphone", "mine"}]
Queries = [{a, e}, {a, p}]

输出：
apple
app

  • 第一行查询1：字符串“apple”是给定字典中唯一具有给定前缀“a”和后缀“e”的单词。
  • 第二行查询2：字符串“app”是给定字典中唯一具有给定前缀“a”和后缀“p”的单词。

1、解决方案 - 朴素方法

# N 是数组中字符串的数量
N = 8  
  
# Declare an array of size N  
arr = ["apple", "app", "biscuit", "mouse", "orange", "bat", "mine", "mine"]  
  
Q = [["a", "e"], ["mi", "ne"]]  
  
for i in range(len(Q)):  
    prefix = Q[i][0]  
    suffix = Q[i][1]  
  
    found = False  
  
    for j in range(N):  
        if arr[j][:len(prefix)] == prefix and arr[j][-len(suffix):] == suffix:  
            print(arr[j])  
            found = True  
            break  
  
    if not found:  
        print("-1")  

Output:
apple
mine

这里的简单方法是将每个字符串的前缀和后缀与相应的查询进行比较。如果前缀和后缀匹配，我们将打印该字符串并将找到的标志设置为 True。否则，如果未找到匹配项，我们将在查询末尾打印“-1”。
时间复杂度 -上述程序的时间复杂度为 O (Q*N*M)，其中 M 是字符串的最大长度。

我们可以用更有效的方法来解决它。

2、解决方案
在本节中，我们将使用 Trie 数据结构来解决这个问题。它可以通过以下方式支持前缀和后缀搜索 -

为了同时支持前缀和后缀搜索，可以将单词“apple”插入到Trie数据结构中。此外，还可以插入单词的变体以促进高效的前缀和后缀搜索。例如，单词“e{apple”、“le{apple”、“ple{apple”、“pple{apple”和“apple{apple”可以插入到 Trie 中。

Trie 中的每个单词都采用“suffix {word”的形式，其中“suffix”表示从给定单词“apple”获得的所有可能的后缀。
插入特殊字符{来分隔后缀和单词来分隔它们。可以使用任何其他特殊字符代替 {，但首选 {，因为它的 ASCII 值为 123。

以下是解决问题的步骤 -

首先，遍历给定数组中的字符串并执行以下步骤 -

  1. 将字符串 temp 初始化为'{' + arr。
  2. 从尾部开始遍历字符串 arr 中的所有字符。将每个字符追加到字符串 temp 的前面，然后将该字符串插入 Trie 数据结构。
  3. 创建 Trie 后，迭代所有查询，并对每个查询执行以下操作：[list=1]
  4. 存储当前查询的前缀和后缀字符串。
  5. 将字符串 t 初始化为后缀 + '{' + 前缀，然后在 Trie 中查找。
  6. 如果在 Trie 中找不到字符串 t，则打印"-1"。
  7. 否则，打印在 Trie 中找到的匹配字符串。

让我们理解下面的例子 ：

class TrieNode:  
    def __init__(self):  
        self.children = {}  
        self.is_end_of_word = False  
  
class Trie:  
    def __init__(self):  
        self.root = TrieNode()  
  
    def insert(self, word):  
        node = self.root  
        for char in word:  
            if char not in node.children:  
                node.children[char] = TrieNode()  
            node = node.children[char]  
        node.is_end_of_word = True  
  
    def search(self, word):  
        node = self.root  
        for char in word:  
            if char not in node.children:  
                return False  
            node = node.children[char]  
        return node.is_end_of_word  
  
def insert_suffixes_into_trie(trie, word):  
    for i in range(len(word) - 1, -1, -1):  
        temp = '{' + word[i:]  
        trie.insert(temp)  
  
def find_matching_word(trie, prefix, suffix):  
    t = suffix + '{' + prefix  
    return trie.search(t)  
  
# Example usage:  
if __name__ == "__main__":  
    words = ["apple"]  
    queries = [["e", "le"], ["pl", "pple"], ["x", "y"]]  
  
    trie = Trie()  
    for word in words:  
        insert_suffixes_into_trie(trie, word)  
  
    for prefix, suffix in queries:  
        if find_matching_word(trie, prefix, suffix):  
            print("Matching word found for prefix '{}' and suffix '{}'.".format(prefix, suffix))  
        else:  
            print("-1")  


在这段代码中，我们首先定义了 TrieNode 和 Trie 类，以创建和使用 Trie 数据结构。插入方法用于在 Trie 中插入单词，搜索方法用于在 Trie 中搜索单词。

insert_suffixes_into_trie() 函数将一个 Trie 和一个单词作为输入，并将该单词所有可能的后缀插入 Trie。

find_matching_word() 函数将 Trie、前缀和后缀作为输入，以 "suffix{prefix "格式构造字符串 t，并在 Trie 中搜索该字符串。

时间复杂度 - 时间复杂度为 O (N*M2 + Q*M)，其中 M 是所有字符串的最大长度。