次のように私は、最初のリストを持っている

Question

最初と最後の共通の文字交差して、リストの削減：

は

ab, aj, ad, ae, bd, bc, bd, bg, bj, dj

アルゴリズムは

を形成するために、このリスト内の要素の最初と最後の共通の文字を交差しなければならないし（結果として）

abd, abj, bdj

、最終的に

abdj

最も長い交差点です。

これを取得するためのアルゴリズムに関する提案はありますか？

Answer 1

単純なグラフ検索のように見えます。ここでは解決策はありませんが、幻想的なものはありません（サイクリックチェック、キャッシングパス）。最適なパフォーマンスのためにこれらを追加する必要があります。これは、そのすべての弱点との完全なグラフ探索（すなわち、組み合わせ爆発、NPなど）があることに注意してください

static List<string> _graph = new List<string>() { "ab", "aj", "ad", "ae", "bd", "bc", "bd", "bg", "bj", "dj" }; 

static void Main(string[] args) 
{ 
    string longest = string.Empty; // Result will be here. 
    foreach (string node in _graph) 
     GenerateChildren(node,ref longest); 
} 

static void GenerateChildren(string parent, ref string longest) 
{ 
    // Store longest path. 
    if (parent.Length > longest.Length) 
     longest = parent; 
    foreach (string child in _graph.Where(child=>parent.EndsWith(child.Substring(0,1)))) 
     GenerateChildren(parent+child.Substring(1),ref longest); 
}