3481. Apply Substitutions

Intuition

We are given placeholders like %a% and a map of replacements. Since a replacement can itself contain other placeholders, we must recursively resolve each key until we get plain text.

To avoid recomputing the same replacements again and again, we use memoization.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N*M)$

Code

// Memoization map to store already resolved substitutions
Map<Character, String> resolvedMapping = new HashMap<>();

// Recursive function to resolve a placeholder completely
public String resolve(Map<Character, String> replacementsMap, char key) {
    if (resolvedMapping.containsKey(key)) 
        return resolvedMapping.get(key);

    StringBuilder resolvedString = new StringBuilder();
    String originalString = replacementsMap.get(key);

    for (int index = 0; index < originalString.length(); ) {
        // If a placeholder pattern like %x% is found
        if (originalString.charAt(index) == '%' && originalString.charAt(index + 2) == '%') {
            char innerKey = originalString.charAt(index + 1);
            resolvedString.append(resolve(replacementsMap, innerKey));
            index += 3; // Skip the %x%
        } else {
            resolvedString.append(originalString.charAt(index));
            index++;
        }
    }

    // Store resolved result for future use
    resolvedMapping.put(key, resolvedString.toString());
    return resolvedMapping.get(key);
}

// Main function to apply all substitutions
public String applySubstitutions(List<List<String>> replacements, String text) {
    // Prepare the replacement map
    Map<Character, String> replacementsMap = new HashMap<>();
    for (List<String> replacement : replacements) {
        replacementsMap.put(replacement.get(0).charAt(0), replacement.get(1));
    }

    StringBuilder finalResult = new StringBuilder();
    for (int index = 0; index < text.length(); ) {
        // If a placeholder pattern like %x% is found
        if (text.charAt(index) == '%' && text.charAt(index + 2) == '%') {
            char key = text.charAt(index + 1);
            finalResult.append(resolve(replacementsMap, key));
            index += 3; // Skip the %x%
        } else {
            finalResult.append(text.charAt(index));
            index++;
        }
    }

    return finalResult.toString();
}