Python中高效实现二元元组链式匹配分组的方法咨询

给定二元元组列表：

str_tuple = [("def","abc"),("ghi","def"),("jkl","ghi"),("bat","cat"),("rat","bat"),("uuu","iii")]

需求是将可链式匹配的元组合并（前一个元组的第一个元素等于后一个元组的第二个元素时，合并为链条首尾组成的元组），孤立元组保持原样，预期输出：

[("jkl","abc"),("rat","cat"),("uuu","iii")]

高效实现方案：利用字典映射构建链式关系 #

无需多重循环，通过两个字典分别记录元组的前后向映射，快速定位链条首尾，时间复杂度为O(n)：

str_tuple = [("def","abc"),("ghi","def"),("jkl","ghi"),("bat","cat"),("rat","bat"),("uuu","iii")]

# 构建前向映射（key: 元组第一个元素, value: 元组第二个元素）
next_map = {}
# 构建反向映射（key: 元组第二个元素, value: 元组第一个元素）
prev_map = {}

for a, b in str_tuple:
    next_map[a] = b
    prev_map[b] = a

result = []

# 遍历所有可能的链条起点（无前驱指向的节点）
for start in next_map:
    if start not in prev_map:
        current = start
        # 沿前向映射走到链条终点
        while current in next_map:
            current = next_map[current]
        # 合并为首尾元组加入结果
        result.append((start, current))

print(result)

方案说明 #

1. 映射构建：通过一次遍历生成两个字典，next_map记录每个节点的下一个节点，prev_map记录每个节点的上一个节点，实现O(1)时间复杂度的节点关系查询。
2. 定位起点：链条的起点是那些仅出现在next_map的key中、但不在prev_map的key中的元素（没有任何元组指向它）。
3. 遍历链条：从起点出发，沿next_map一直走到无后续节点的终点，直接合并首尾得到最终元组。
4. 孤立元组处理：像("uuu","iii")这类孤立元组，其起点uuu不在prev_map中，终点iii也不在next_map中，会被自动识别为独立链条并保留。

内容的提问来源于stack exchange，提问作者Sjn73