检查是否可以链接字符串列表

Question

题

实现一个函数bool chainable(vector<string> v),它接受一组字符串作为参数,并返回true它们是否可以链接.如果第一个字符串以第二个字符串开头的相同字符结尾,则可以链接两个字符串,例如:

ship->petal->lion->nick  = true;
ship->petal   axe->elf   = false;

我的解决方案

我的逻辑是,如果它的可链接只有一个不匹配的开始和结束.所以我创建了一个开始列表和一个结束列表.像这样.

starts:s,p,l,n
ends:  p,l,n,k

如果删除公共元素,列表最多应包含一个项目.即s和k.如果是这样,列表是可链接的.如果列表是循环的,则最终列表为空.

但我想我在这里遗漏了一些案例,

编辑: 好的,我的解决方案有问题.我们能否为此得出最佳算法？

Answer 1

问题是检查有向图中是否存在欧拉路径,其顶点是作为至少一个提供的单词的第一个或最后一个字母出现的字母,其边是提供的单词(每个单词是其第一个字母的边缘)到最后).

在这些图中存在欧拉路径的一些必要条件:

1. 必须连接图表.
2. 具有最多两个异常的所有顶点具有相同数量的传入和传出边缘.如果存在特殊顶点,则恰好有两个,其中一个具有比传入更多的传出边缘,另一个具有比传出更多的传入边缘.

很容易看出必要性:如果图形具有欧拉路径,则任何此类路径都会遇到除孤立顶点之外的所有顶点(既不是传出边也不是传入边).通过构造,这里考虑的图中没有孤立的顶点.在欧拉路径中,每次访问顶点时,除了开始和结束之外,都使用一个入射边缘和一个出射边缘,因此每个顶点可能除了起始和结束顶点之外具有相同的入射和出射边缘.除非Eulerian路径是一个循环,否则起始顶点比传入顶点有一个更多的出局边缘,而结尾顶点多一个出局边缘,在这种情况下,所有顶点都有相同的输入和输出边缘.

现在重要的是这些条件也足够了.人们可以通过感应来证明边缘的数量.

这样可以进行非常有效的检查:

• 记录从单词中获得的所有边和顶点
• 使用联合查找结构/算法来计算图的连接组件
• 记录indegree - outdegree所有顶点

如果number of components > 1(至少)有一个顶点|indegree - outdegree| > 1或者顶点有两个以上的顶点indegree != outdegree,则这些单词不可链接,否则它们是可链接的.

Answer 2

这与臭名昭着的旅行推销员问题不是很相似吗？

如果你有n字符串,你可以用它们构造一个图形,其中每个节点对应一个字符串.您可以通过以下方式构造边:

• 如果string(resp.node)a并且b是可链接的,则引入a -> b具有权重的边1.
• 对于所有unchainable字符串(分别为节点)a和b,你介绍一个边缘a -> b与重量n.

然后,当且仅当您可以在权重小于的图中找到最佳TSP路线时,所有字符串都是可链接的(不重复)2n.

注意:您的问题实际上比TSP更简单,因为您始终可以将字符串链接转换为TSP,但不一定相反.