string - 找到每个词的频率

Question

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

问题是:

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

我的做法:用了trie，Suffix tree，面试官不是很满意。你能给我一个给定问题的算法吗？

Answer 1

下面如何...求一个字符串 s 在有向图中出现的次数。

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

注意事项

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

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

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