寻找每个单词的频率

Question

在面试中有一个问题问到我，但我没有能够回答。

问题是：

给定一个有向图，其中每个节点都是一个字符，并且还给定一个字符串数组。任务是通过在图中搜索来计算数组中每个字符串的频率。

我的方法：我使用了trie和后缀树，但面试官并不完全满意。你能为这个问题提供一个算法吗？

- devsda

---

给定的图结构是什么？ - aioobe

可能包含环的有向图。 - devsda

一个任意的有向图？所以每个节点包含一些随机字符，所有边缘都是随机分布的？你的问题没有意义。 - aioobe

这个问题不太清楚。提问者暗示你可以通过搜索图形来确定数组中字符串的频率，但并没有说明图形与字符串之间的关系。例如，如果数组是{ dog，cat，bird，dog，fish，cat，apple，dog，cat }，那么图形是什么？ - Tyler Durden

请注意，您的图形基本上是一个确定有限状态自动机（也称为最终状态机）。 - amit

Answer 1

以下是一种方法，可以在有向图中查找字符串s的出现次数：

1. 从广度优先搜索开始（标记已访问的节点以避免循环）。 2. 当找到第一个字符时，切换到深度优先搜索，并将最大深度设置为s的长度。 3. 如果检测到字符串序列，则对DFS的每个出现次数增加出现次数计数。 4. 恢复BFS。

以下是一些注意事项：

1. 我认为DFS不应该共享BFS的已访问节点列表（例如，您可能需要返回到开头并重叠）。 2. BFS也不应该共享DFS的已访问列表。例如，您可能正在寻找“Alan”，并且有“AAlan”，确保您在第二个A上重新开始。

对于数组，我可以为每个字符串重复此过程。当然，可能会有更有效的解决方案，但我会从这种方式开始思考。

如果你的答案包括关于广度优先搜索或深度优先搜索的任何对话吗？如果有人提到搜索图，我几乎总是会回复其中一个变体。

- Alan

Answer 2

这是另一种解决方案：

首先，我们需要对字符串数组进行一些预处理。 让我们将C定义为数组中所有字符串组成的字符的子集。 对于C中的每个字符，我们将跟踪包含该字符的每个字符串及其在该字符串中的位置以及一个布尔值，指示它是否是该字符串中的最后一个字符。 这可以使用字典完成。

例如，假设我们的数组是['one', 'two', 'three']。 我们的字典看起来像这样：

'o': (0, 0, false),(1,2,true)
't': (1, 0, false),(2,0,false) 
'n': (0, 1, false)
'e': (2, 3, false),(2,4, true)
'h': (2, 1, false)
'r': (2, 2, false)
'w': (2, 1, false)

接下来我们将使用DFS和动态规划。基本上，每当您访问一条边时，您都会检查字典中的父项和子项，以查看它们是否组成一个子字符串，并存储该信息。

使用此方法，您可以轻松检测数组中每个字符串的所有重复出现。

构建预处理表可以在o（L）内完成，其中L是数组中所有字符串长度的总和。

发现所有重复出现可以在O（m * k）内完成，其中m是边的数量（而不是节点的数量，因为节点可能会被多次发现），k是字符串的数量。

实现可能有些棘手，有一些陷阱需要避免。

- Samy Arous

Answer 3

看这张图，每个层级都有所有的4*4边缘（很难画，请谅解）。

可能会有很多次出现。

我认为他可能期望使用动态规划：

单独处理每个字符串，f[i][j]表示从节点i开始完成字符串的最后j个字母的总数，其余部分将很容易解决。

- iloahz