递归解析字符串百分号占位符的最优实现方案及时间复杂度分析

现有代码问题 #

• 按空格拆分字符串的逻辑错误：占位符可能和非空格字符（如标点、其他普通字符）拼接出现，按空格拆分无法正确识别这类占位符
• 遍历拆分数组时修改的是局部变量word，无法回写到原数组st，最终拼接结果不会用到修改后的值
• 第二个循环的st.contains("%")逻辑完全错误：st是字符串数组，该判断是检查数组中是否存在值为%的元素，而不是检查当前单词是否包含占位符
• 直接修改输入的HashMap会污染原始映射表，若其他逻辑也用到该映射表会出现不可预期的错误
• 未处理循环依赖场景：如果出现A→%B%、B→%A%的映射，会触发无限递归导致栈溢出
• 没有正确提取占位符名称的逻辑：代码里调用的parse方法没有给出实现，无法正确从带%的字符串中提取对应的映射键

优化实现方案 #

推荐用正则匹配+记忆化缓存+循环依赖检测的方案，不需要按空格拆分，适配所有占位符出现的场景，实现如下：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class PlaceholderResolver {
    // 匹配%xxx%格式的占位符
    private static final Pattern PATTERN = Pattern.compile("%(\\w+)%");
    // 单独的记忆化缓存，不污染原始映射表
    private HashMap<String, String> cache;
    // 循环依赖检测集合
    private Set<String> resolving;

    public String resolve(String s, HashMap<String, String> mapping) {
        cache = new HashMap<>();
        resolving = new HashSet<>();
        return resolveString(s, mapping);
    }

    private String resolveString(String str, HashMap<String, String> mapping) {
        Matcher matcher = PATTERN.matcher(str);
        StringBuffer sb = new StringBuffer();
        while (matcher.find()) {
            String key = matcher.group(1);
            // 先查缓存，已经解析过的直接用
            String value = cache.get(key);
            if (value == null) {
                // 检查循环依赖
                if (resolving.contains(key)) {
                    throw new IllegalArgumentException("检测到循环依赖，占位符：" + key);
                }
                resolving.add(key);
                // 原始映射里没有的键，保留原占位符
                String rawValue = mapping.getOrDefault(key, matcher.group());
                // 递归解析值里的占位符
                value = resolveString(rawValue, mapping);
                cache.put(key, value);
                resolving.remove(key);
            }
            matcher.appendReplacement(sb, Matcher.quoteReplacement(value));
        }
        matcher.appendTail(sb);
        return sb.toString();
    }
}

该实现的优势：

• 用正则匹配所有符合规则的占位符，不需要依赖空格分割，适配任意场景
• 单独的缓存不污染原始映射表，每个占位符仅需要解析一次
• 加入循环依赖检测，避免无限递归
• 替换逻辑直接在匹配过程中完成，不需要两次遍历数组拼接，性能更高

时间复杂度计算 #

• 无记忆化的递归实现：最坏时间复杂度为O(d * L)，其中d是替换的最大深度，L是输入字符串的总长度。如果出现大量重复的占位符，每次遇到都要递归解析，会有大量重复计算。
• 带记忆化的优化实现：最坏时间复杂度为O(n + k)，其中n是最终输出字符串的总长度，k是不同占位符的数量。每个占位符只会被解析一次，每个字符最多被处理两次（匹配阶段+拼接阶段），没有重复计算。

示例测试结果 #

针对你给出的映射表和输入字符串（注：原示例里的%Intro缺了闭合的%，补全为%Intro%后），最终替换结果为：

Give Your Hello My Name is Tom Johnson and I am x Year old Tom Johnson

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