面接で質問がありましたが、答えられません。
質問は：
すべてのノードが文字である有向グラフが与えられ、文字列の配列も与えられます。タスクは、グラフを検索して、配列内のすべての文字列の頻度を計算することです。
私のアプローチ：トライ、サフィックスツリーを使用しましたが、インタビュアーは完全に満足していません。与えられた問題のアルゴリズムを教えてください。
3 に答える
1
以下はどうでしょう... 有向グラフで文字列 s の出現回数を求めるには。
- ブレッド ファースト検索から開始します (サイクルを避けるために、既にアクセスしたノードをマークします)。
- 最初の文字が見つかったら、max-depth = length(s) の深さ優先検索に切り替えます
- 文字列シーケンスが検出された場合、DFS が発生するたびに発生回数を増やします
- BFS を再開する
いくつかの注意事項
- DFS が BFS の訪問済みノード リストを共有する必要があるとは思いません (たとえば、最初に戻ってオーバーラップする必要がある場合があります)。
- BFS は、DFS の訪問済みリストも共有すべきではありません。たとえば、「Alan」を探していて「AAlan」があり、2 番目の A で再起動するようにすることができます。
配列の場合、文字列ごとにこの手順を繰り返すことができます.確かにもっと効率的な解決策があるかもしれませんが、私はこのように考え始めます..
あなたの回答には、幅優先検索または深さ優先検索に関する会話が含まれていましたか? 誰かがグラフの検索について言及した場合、私はほとんどの場合、これらのいずれかのバリエーションで返信します
于 2012-10-19T14:06:34.290 に答える
0
このグラフを参照してください。各レベルにはすべて 4*4 のエッジがあります (描くのが難しいので、我慢してください)
発生が多いかもしれません。
私は彼が期待しているかもしれないと思うdynamic programming：
各文字列を個別に処理し、 node から始まる文字f[i][j]列の最後の文字を達成するための総数を示します。残りは簡単です。ji
于 2012-10-20T16:29:09.380 に答える