主页 / 问题 / 1213335
Accepted
DGDays
Asked:2021-12-03 15:32:17 +0000 UTC2021-12-03 15:32:17 +0000 UTC

如何比较多个字符串并找到正确的序列？

  • 772

行数n也来自输入。n-ое字符串由英文字母表中的字母序列组成。任务是选择这样一个序列，使每一行的开头与另一行的结尾重合（取 3 个字符来检查）。答案应显示在一行上，指明以什么顺序输出初始行序列。

如何实施？

我只是想出了如何接受这些行：

n = int(input())
spis = []
for i in range(0,n):
    c = input()
    spis.append(c)

但我不能再进一步了。不知道（

用标准方法写Python

这就是我获得兼容列表的方式，而不是：

a = int(input())
spis = []
res = ""
good = {}
bad = {}
for i in range(0,a):
    c = input()
    spis.append(c)
for i in spis:
    for c in range(0,len(spis)):
        if (i[:3] == spis[c][-3:]) and (i!=spis[c]):
            good.update({spis[c]:i})
        else:
            bad.update({spis[c]:i})

现在如何从这里显示适当的字符串并形成所需的字符串？

python

1 个回答

  1. Best Answer

    我把一切都搞砸了，没必要......

    有必要建立一个有向图，其中节点是三个字符的结束和开始，弧是原始线。如果字符串以 'abc' 结尾，则它是 'abc' 的传入边（弧），如果它开始，则它是传出边。

    然后为结果图找到欧拉路径e-maxx , itmo

    留下旧答案

    检查每条线，其起点与终点重合，并构造一个有向图，其中节点是线，弧是匹配的。

    该图可能看起来像一个邻接列表（列表列表A[][]_，因为第 i 行A[i]包含与末尾兼容的行号列表spis[i]

    a = int(input())
spis = []
for i in range(a):
    spis.append(input())

A =[[] for _ in range(len(spis))]
for i in range(len(spis)):
    for c in range(len(spis)):
        if (spis[i][:3] == spis[c][-3:]) and (i!=c):
             A[c].append(i)
print(A)


4
123456
456789
456999
999123

[[1, 2], [], [3], [0]]

    然后找到给定图的欧拉路径。网络上有很多关于算法的描述，在Python中可以使用networkx.eulerian_path

    • 2

相关问题