N Stage字符串压缩场景下的最优解压实现算法求解

需求前提梳理 #

给定的压缩规则为将长字符串映射为单个短标记字符（如示例中Adsddf→?、ds?xsc→:、csdcs:→#），解压要求为逐位原地替换，直到字符串中不存在可替换的标记字符为止。

最优算法选择：基于反向字典的栈遍历方案（时间复杂度O(L)，L为最终输出字符串长度） #

该方案避免了暴力替换需要多轮扫描字符串的额外开销，嵌套层级再多也不会重复遍历，是当前需求下效率最高的实现方式。

算法步骤 #

• 第一步：预处理映射规则，构建反向替换字典+标记集合：把原映射的键值反转，得到{标记字符: 对应的原长字符串}的映射关系，同时把所有标记字符存入Hash集合，实现O(1)时间判断字符是否为可替换标记。
• 第二步：通过栈结构单次遍历输入字符串：
  1. 从左到右逐个取出输入字符串的字符，压入栈顶
  2. 每次压入后检查栈顶字符是否属于标记集合：
     • 如果不是，继续压入下一个字符
     • 如果是，弹出栈顶的标记字符，将该标记对应的原长字符串逐个按顺序压入栈，每压入一个字符就重新检查新的栈顶是否为标记，是就重复弹出替换操作
• 第三步：遍历完成后，将栈内所有字符拼接，得到最终解压结果

算法优势 #

• 时间效率最优：每个字符最多入栈、出栈各1次，整体时间复杂度和最终输出字符串长度线性相关，无额外扫描开销
• 空间可控：除输出结果占用的空间外，仅额外存储反向字典和标记集合，空间复杂度为O(n + L)，n为映射条目数，L为输出长度

示例验证（对应题目给出的输入用例） #

输入字符串：ac3d:cs?
反向字典：{'?': 'Adsddf', ':': 'ds?xsc'}
执行过程：

1. 依次压入a、c、3、d，栈顶均不是标记，继续
2. 压入:，判定为标记，弹出:后依次压入d、s、?
3. 压完?后判定栈顶为标记，弹出?后依次压入A、d、s、d、d、f，栈顶f不是标记，继续
4. 依次压入c、s，栈顶不是标记，继续
5. 压入?，判定为标记，弹出?后依次压入A、d、s、d、d、f
6. 遍历完成，栈拼接结果为ac3ddsAdsddfxsccsAdsddf，和示例输出完全匹配

代码实现参考（Python为例） #

def decompress(input_str, original_mapping):
    # 构建反向替换字典和标记集合
    reverse_map = {v: k for k, v in original_mapping.items()}
    markers = set(reverse_map.keys())
    stack = []
    for c in input_str:
        stack.append(c)
        # 循环处理栈顶的可替换标记
        while stack and stack[-1] in markers:
            marker = stack.pop()
            # 将替换字符串逐个压入栈
            for char in reverse_map[marker]:
                stack.append(char)
    return ''.join(stack)

# 示例测试
if __name__ == "__main__":
    test_mapping = {
        "Adsddf": "?",
        "ds?xsc": ":",
        "csdcs:": "#"
    }
    test_input = "ac3d:cs?"
    print(decompress(test_input, test_mapping))
    # 输出：ac3ddsAdsddfxsccsAdsddf

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