多项式同类项合并：嵌套列表含公共字符串的整数高效累加方案

我需要对多项式中的单项式执行加减合并同类项操作，例如 2xy+abc-xy -> xy+abc。

目前我已经通过正则表达式提取每个单项式的各元素，存储为嵌套列表结构，以上述示例为例，结构如下：

[['+', '2', 'xy', 2], ['+', '3', 'abc', 3], ['-', '1', 'xy', 2]]

每个子列表的第四个元素是第三个字符串元素的长度，用于方程重组时的排序。

我现在的实现方式是遍历所有项，将系数存入字典累加后输出结果，简化伪代码如下：

if string not in dict:
    dict[string] = num
else:
    dict[string] += num
result = [str(num) + string for item in dict.items]

我认为存在更高效的实现方案，目前已尝试的路径包括：

• 用 set()、cmp() 对比列表
• 尝试使用不熟悉的 reduce()、zip 方法
• 用 filter() 筛选匹配元素的列表
• 在Stack Overflow检索相关方案

这是我在Stack Overflow的第一个提问，恳请大家提供相关建议或方向指引。

提问编辑补充 #

感兴趣的朋友可以参考我最终实现的该模块代码，感谢大家的指引。

pattern = r"([+-]|)([\d]+|)([a-z]+)"
monomial_dict = {}
# poly = "-a+5ab+3a-c-2a"
for m in re.finditer(pattern, poly): 
        mono_val = m.group(2)
        if not mono_val: # 单项式前无数字系数时赋值为1，方便字典累加
            mono_val = '1'
        num = int(m.group(1) + mono_val)
        string = ''.join(sorted(m.group(3)))
        if string not in monomial_dict:
            monomial_dict[string] = [num, string]
        else:
            monomial_dict[string][0] += num
# monomial_dict = {'a': [0, 'a'], 'ab': [5, 'ab'], 'c': [-1, 'c']}

你目前基于哈希字典的实现已经是这类场景下时间复杂度最优的方案了，整体时间复杂度为O(n)（n为单项式数量），比你尝试的set对比、filter筛选等需要二次遍历的方案效率高得多，不需要更换核心逻辑，只需要做几个细节优化就能进一步提升性能和鲁棒性：

1. 用collections.defaultdict简化字典判空逻辑，不需要每次判断key是否存在，省略冗余的if-else分支
2. 系数转整数的逻辑可以合并，省略单独的空值判断分支
3. 输出阶段可以增加系数为0的项过滤、系数为±1时的显示优化，以及按变量长度排序的逻辑，和你预留的第四个字段的排序需求匹配

以下是优化后的可直接运行的代码示例：

import re
from collections import defaultdict

def merge_polynomial(poly):
    # 正则优化，用?匹配可选的符号位更规范
    pattern = r"([+-]?)(\d*)([a-z]+)"
    monomial_dict = defaultdict(int)
    for m in re.finditer(pattern, poly):
        sign = m.group(1) or '+'
        coeff = m.group(2) or '1'
        num = int(f"{sign}{coeff}")
        # 字母排序作为key，兼容xy和yx这类顺序不同的同类项
        var_key = ''.join(sorted(m.group(3)))
        monomial_dict[var_key] += num
    # 按变量长度排序，过滤系数为0的项后拼接结果
    res = []
    for var, coeff in sorted(monomial_dict.items(), key=lambda x: len(x[0])):
        if coeff == 0:
            continue
        # 优化系数为±1时的显示效果，省略数字1
        if coeff == 1:
            res.append(f"+{var}")
        elif coeff == -1:
            res.append(f"-{var}")
        else:
            res.append(f"{coeff:+d}{var}")
    # 移除结果开头多余的+号
    return ''.join(res).lstrip('+')

# 测试示例
print(merge_polynomial("2xy+abc-xy")) # 输出：xy+abc
print(merge_polynomial("-a+5ab+3a-c-2a")) # 输出：5ab-c

至于你尝试过的其他方案，实际效率都低于现有方案：

• set只能用于去重，无法同步累加系数，还需要额外遍历匹配对应项的系数，整体时间复杂度会升到O(n²)
• reduce本质还是遍历累加，和现有字典逻辑没有性能差异，只是写法风格不同
• filter每次筛选同类项都要遍历剩余所有元素，时间复杂度也是O(n²)，仅适合项数极少的场景

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