面试中有一个问题问我,但我无法回答。
问题是:
给定一个有向图,其中每个节点都是一个字符,同时给定一个字符串数组。 任务是通过在图中搜索来计算数组中每个字符串的频率。
我的做法:用了trie,Suffix tree,面试官不是很满意。你能给我一个给定问题的算法吗?
最佳答案
下面如何...求一个字符串 s 在有向图中出现的次数。
- 从面包优先搜索开始(标记已经访问过的节点以避免循环)
- 当找到第一个字符时,切换到深度优先搜索,max-depth = length(s)
- 如果检测到字符串序列,则为 DFS 的每次出现增加出现次数
- 恢复 BFS
注意事项
- 我不认为 DFS 应该共享 BFS 的已访问节点列表(例如,您可能需要回到开头并重叠
- BFS 也不应该共享 DFS 访问列表。例如,您可能正在寻找“Alan”并找到“AAlan”,并确保在第二个 A 上重新开始
现在对于一个数组,我可以为每个字符串重复这个过程。当然可能有更有效的解决方案,但我会以这种方式开始考虑。
您的回答是否包含有关广度优先或深度优先搜索的任何对话?如果有人提到要搜索图表,我几乎总是会用其中一个的变体来回复
关于string - 找到每个词的频率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12973622/