3

面试中有一个问题问我，但我无法回答。

问题是：

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

我的做法：我用了trie、Suffix tree，但面试官并不完全满意。你能给我一个给定问题的算法吗？

4

3 回答 3

1

下面怎么样...在有向图中查找字符串 s 的出现次数。

  • 从面包优先搜索开始（标记已经访问过的节点以避免循环）
  • 找到第一个字符后，切换到深度优先搜索，max-depth = length(s)
  • 如果检测到字符串序列，则为每次出现的 DFS 增加出现次数
  • 恢复 BFS

一些注意事项

  • 我不相信 DFS 应该共享 BFS 的访问节点列表（例如，您可能需要回到开头并重叠
  • BFS 也不应该共享 DFS 访问列表。例如，您可能正在寻找“Alan”并拥有“AAlan”，并确保从第二个 A 重新开始

现在对于一个数组，我可以对每个字符串重复这个过程。当然可能有更有效的解决方案，但我会开始这样想。

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

于 2012-10-19T14:06:34.290 回答
0

这是另一个解决方案：

首先我们需要对字符串数组做一些预处理。让我们将 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 和动态规划。基本上，每当您访问边缘时，您都会检查 dict 上的父项和子项，以查看它们是否构成子字符串并存储该信息。

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

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

发现所有递归可以在 O(m * k) 中完成，其中 m 是边的数量（而不是节点的数量，因为一个节点可以被多次发现），k 是字符串的数量。

实现可能有点棘手，您应该避免一些陷阱。

于 2012-10-19T15:05:23.920 回答
0

看这张图，每个级别都有所有 4*4 边（很难画，请支持我）

在此处输入图像描述

可能会出现很多情况。

我想他可能期待dynamic programming：

单独处理每个字符串，表示从 node 开始f[i][j]完成字符串最后一个字母的总数，其余的很容易。ji

于 2012-10-20T16:29:09.380 回答