在字典中按给定前缀和后缀搜索字符串

在本教程中，我们将编写 Python 程序，以在字典中带有给定前缀和后缀的字符串搜索。我们给出了一个包含 N 个字符串和 Q 个查询的数组，查询格式为两个字符串 prefix 和 suffix。我们的任务是找到给定数组中带有给定前缀和后缀的任何字符串。

让我们理解以下示例 -

输入

arr = ["apple", "app", "biscuit", "mouse", "orange", "bat", "microphone", "mine"}]

Queries = [{a, e}, {a, p}]

输出

apple

app

说明

查询 1

字符串“apple”是给定字典中唯一带有给定前缀“a”和后缀“e”的单词。

查询 2

字符串“app”是给定字典中唯一带有给定前缀“a”和后缀“p”的单词。

让我们用朴素的方法来解决这个问题。

解决方案 - 朴素方法

输出

apple
mine

解释 -

朴素方法涉及将每个字符串的前缀和后缀与相应的查询进行比较。如果前缀和后缀匹配，则打印字符串并将 found 标志设置为 True。否则，如果在查询结束时未找到匹配项，则打印“-1”。

时间复杂度 - 上述程序的时​​间复杂度为 O (Q*N*M)，其中 M 是字符串的最大长度。

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

解决方案 -

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

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

Trie 中的每个单词的格式将是“suffix {word”，其中“suffix”表示从给定单词“apple”获得的所有可能的后缀。

插入特殊字符 { 是为了分隔后缀和单词。可以用任何其他特殊字符代替 {，但首选 {，因为它的 ASCII 值是 123。

以下是解决问题的步骤 -

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

1. 将字符串 temp 初始化为 '{' + arr[i]。
2. 从末尾开始迭代字符串 arr[i] 中的所有字符。对于每个字符，将其附加到字符串 temp 的开头，然后将此字符串插入 Trie 数据结构。
3. 创建 Trie 后，遍历所有查询，对于每个查询，执行以下操作
   1. 存储当前查询的前缀和后缀字符串。
   2. 将字符串 t 初始化为 suffix + '{' + prefix，并在 Trie 中搜索它。
   3. 如果在 Trie 中找不到字符串 t，则打印“-1”。
   4. 否则，打印在 Trie 中找到的匹配字符串。

让我们理解以下示例 -

示例 -

输出

apple
mine

解释 -

在此代码中，我们首先定义 TrieNode 和 Trie 类来创建和使用 Trie 数据结构。insert 方法用于将单词插入 Trie，search 方法用于在 Trie 中搜索单词。

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

find_matching_word() 函数接受 Trie、前缀和后缀作为输入，以“suffix{prefix”的格式构造一个字符串 t，并在 Trie 中搜索它。

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

结论

总之，本文讨论了使用 Trie 数据结构有效地同时支持给定单词集的前缀和后缀搜索的概念。Trie 是一种类似树的数据结构，特别适用于处理和搜索大量字符串。