0

我没有过多地使用排序和算法，并且对向量很好。最近我遇到了一个有趣的问题，想请教您如何解决它。所以，下面是我的问题。

问，我在一个向量中获得了 4 个字符串，并且必须根据这些字符的特定顺序排列这些字符串。因此，任何字符串的最后一个字符都应该与任何其他字符串的第一个字符匹配，并且该字符串的最后一个字符应该与任何其他字符串的第一个字符匹配，这样我必须创建一个可能最长的字符串。

例如，如果我有一个像“ABCD”“TGHI”“DADC”“IYUR”“CXYT”这样的字符串向量，那么它将像“ABCD”那样排列，那么会有第三个字符串“DADC”然后会有第五个字符串"CXYT" 等等 所以，结果将是 "ABCD""DADC""CXYT""TGHI""IYUR"。

现在，我想知道根据上述规则检查每个字符串与其他字符串是否“兼容”是否是个好主意。所以如果我在向量中有 5 个字符串，那么我将有 5+4+3 +2+1 可能性，如果例如我有 20 个字符串，那么它会增加很多，所以这是一个好主意还是有任何其他有效的解决方案...非常感谢，希望（大部分）你能理解。

4

2 回答 2

1

将每个字母想象成图中的一个节点。每个单词代表两个字母之间的有向路径。“ACCA”定义 A->A “BAAC”B-->C 。在此图中，您想找到一条欧拉路径。http://en.wikipedia.org/wiki/Eulerian_path 。欧拉路径被定义为只访问每条边一次的路径，因为每条边代表一个词，这意味着您已经使用了所有词！

于 2012-02-09T19:42:08.303 回答
0

更好的方法可能是使用字符串构建有向图。如果 的最后一个字符与的第一个字符相同，则从一个字符串s1到另一个字符串会有一条边。然后你可以尝试在图中找到最长的路径。s2s1s2

于 2012-02-09T19:37:50.607 回答