通过与第一个和最后一个常用字符相交来减少列表

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);
}