题目重点：把 (start_tag,end_tag,payload) 片段视为带身份的图边，用欧拉路径拼完所有片段；分清单向和可反向以及多链的不确定性。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- Q1/Q2 训练版每个输入片段必须恰好使用一次，存在一条覆盖全部片段的单链；同标签可重复出现，故每个片段以 edgeId 区分。
- Q2 反转的是片段在标签图中的方向；payload 仍作为原字符串追加，题目只说正向或反向拼接，并未定义 payload 字符反转。
- 没有指定多个合法链的优先级，返回任意一条；空输入返回空串。
- Q3 的“多条链”没有说明分叉、孤立环和输出次序；正文给出先问清规则后的分解方案，不将其伪装为唯一原题接口。
解题路线
- 把每个片段当有向边 start→end，边保存 payload 与唯一 ID。Q1 是使用所有边一次的有向欧拉路径；标签相同是顶点相同，重复片段仍是不同边。
- 先验入度/出度：若是路径，恰好一个顶点 out−in=1、一个 in−out=1，其余平衡；若是环，所有顶点平衡。从合适起点做迭代 Hierholzer，回退时收集入边并反转。
- Q2 把每片段视为无向边，选择两个奇度顶点之一为起点；若全偶则从任意有边顶点出发。两端邻接表都放同一 edgeId，用 used 位避免一片段走两次。
- 最后必须验证已收集边数等于总片段数；局部满足度数但多个不连通分量时不能拼成单链。
- Q3 如果面试官确认每个连通分量各是一条无分叉链，可对每个分量独立验证欧拉条件并输出。若一个分量里有多个可选拆分，需先确认要最少链数、全部可能链还是任意分解，复杂度与输出完全不同。
手动走一遍
题目四片段从 XXX 起依次经 ATG、GCA、TAG 到 YYY，按边的 payload 得 HelloWorld!Done。Q2 如整体反向走，片段顺序反转，得到 Done!WorldHello；无需把 'Done' 变成 'enoD'。若多给一条 Z→W，不连通检查应拒绝单链问题，而不是悄悄丢掉它。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
def join_fragments(fragments: list[tuple[str, str, str]], reversible: bool = False) -> str:
"""Use every fragment exactly once in one Euler trail; payload is unchanged if reversed."""
if not fragments:
return ""
adjacency: dict[str, list[tuple[str, int]]] = defaultdict(list)
degree: dict[str, int] = defaultdict(int)
for edge_id, (start, end, _) in enumerate(fragments):
adjacency[start].append((end, edge_id))
degree[start] += 1
degree[end] -= 1
if reversible:
adjacency[end].append((start, edge_id))
if reversible:
odd = sorted(node for node in set(degree) | set(adjacency)
if len(adjacency[node]) % 2)
if len(odd) not in (0, 2):
raise ValueError("no single undirected chain")
start_node = odd[0] if odd else min(adjacency)
else:
plus = [node for node, balance in degree.items() if balance == 1]
minus = [node for node, balance in degree.items() if balance == -1]
if any(abs(balance) > 1 for balance in degree.values()) or len(plus) != len(minus) or len(plus) > 1:
raise ValueError("no single directed chain")
start_node = plus[0] if plus else min(node for node, edges in adjacency.items() if edges)
used = [False] * len(fragments)
stack = [(start_node, -1)]
edge_order = []
while stack:
node, incoming = stack[-1]
while adjacency[node] and used[adjacency[node][-1][1]]:
adjacency[node].pop()
if adjacency[node]:
next_node, edge_id = adjacency[node].pop()
if not used[edge_id]:
used[edge_id] = True
stack.append((next_node, edge_id))
else:
stack.pop()
if incoming >= 0:
edge_order.append(incoming)
if len(edge_order) != len(fragments):
raise ValueError("fragments do not form one connected chain")
edge_order.reverse()
return "".join(fragments[edge_id][2] for edge_id in edge_order)
if __name__ == "__main__":
sample = [("XXX", "ATG", "Hello"), ("ATG", "GCA", "World"),
("GCA", "TAG", "!"), ("TAG", "YYY", "Done")]
assert join_fragments(sample) == "HelloWorld!Done"
复杂度
设 E 为片段数、V 为不同 tag 数。建邻接表和迭代欧拉遍历 O(V+E) 时间与空间；Q2 每条边在两侧邻接各存一次，仍是 O(V+E)。最终 payload 拼接需要 O(总输出字符数)。如果需要按指定字典序选链，要对邻接边排序，可能增至 O(E log E)。
易错点与追问
容易失分的边界
- 假设每个 tag 唯一，用 tag→片段的单值字典覆盖重复边。
- Q2 在两个端点各放一条边却没用统一 edgeId，导致一片段被消费两次。
- 只检查入出度，不检查所有边都实际走到。
- 把反向使用片段误解为反转 payload 字符；题目没有这个规则。
- Q3 未定义多链分解时，直接返回一个自选格式并声称是完整原题。
继续深挖
- 如何输出具体片段 ID 顺序并验证每一处标签相接？
- 如 tag 可重复且需要字典序最小拼接，排序应作用于标签、payload 还是原片段 ID？
- Q3 如果有分叉且要最少链数，欧拉路径覆盖如何推广？
- 片段流式到达、随时查询当前链时如何处理合并和环？
