不使用replace或正则替换两%间同名变量对应子串

示例输入 #

user = 'Peter'
location = 'Quahog'
friend = 'Stewie'
string = 'my name is %user% and i live in %location%, and my son is %friend%.'

预期输出 #

my name is Peter and i live in Quahog, and my son is Stewie.

实现要求 #

• 算法时间复杂度为O(N)
• 支持任意数量的待替换变量
• 允许%符号出现在单词内部
• 禁止使用replace方法及正则表达式完成功能

实现方案 #

采用单遍扫描逻辑处理字符串，全程仅遍历一次输入串：

1. 维护状态标记判断当前是否处于占位符收集阶段，分别用列表缓存当前识别到的占位符键名、最终输出结果
2. 逐字符遍历处理：
   • 遇到%时，如果当前不在占位符收集状态，切换状态开始收集键名；如果当前处于收集状态，说明遇到占位符闭合标记，取出缓存的键名去变量映射表查找对应值，存在就将替换值加入结果，不存在就保留原占位符格式，之后退出占位符收集状态
   • 遇到其他字符时，如果在收集占位符键名就把字符加入键名缓存，否则直接加入结果缓存
3. 遍历结束后如果还处于占位符收集状态，说明存在未闭合的%，将残留的未闭合内容原样加入结果即可
   该逻辑不会误判单词内部的单个%，每个字符仅处理一次，时间复杂度稳定为O(N)，变量通过字典传入，支持任意数量的替换项。

可运行代码 #

def render_template(template: str, var_map: dict) -> str:
    res = []
    collect_key = False
    current_key = []
    for c in template:
        if c == '%':
            if not collect_key:
                collect_key = True
                current_key.clear()
            else:
                key = ''.join(current_key)
                res.append(var_map.get(key, f'%{key}%'))
                collect_key = False
        else:
            if collect_key:
                current_key.append(c)
            else:
                res.append(c)
    # 补全末尾未闭合的占位符内容
    if collect_key:
        res.append(f'%{"".join(current_key)}')
    return ''.join(res)

# 示例调用
if __name__ == '__main__':
    variables = {
        'user': 'Peter',
        'location': 'Quahog',
        'friend': 'Stewie'
    }
    raw = 'my name is %user% and i live in %location%, and my son is %friend%.'
    print(render_template(raw, variables))

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