3481. Apply Substitutions

T: O(t + n), n is number of "chars" replacement, t is Length of the original input text, 
because we walk through t chars, and replacement n chars
ex: abc_%B%
T: is abc_ + char number of (%B%) -> is 3 -> so totally is 4 + 3

S: O(n + s + r), n of replacement for map, s: recusion stack , r: StringBuilder result

class Solution {
    public String applySubstitutions(List<List<String>> replacements, String text) {
        Map<String, String> replaceMap = new HashMap<>();
        for (List<String> replacement : replacements) {
            replaceMap.put(replacement.get(0), replacement.get(1));
        }
        Map<String, String> memo = new HashMap<>();
        return dfs(replaceMap, text, memo);
    }
    private String dfs(Map<String, String> replaceMap, String text, Map<String, String> memo) {
        if (memo.containsKey(text)) {
            return memo.get(text);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < text.length(); i++) {
            if (text.charAt(i) != '%') {
                sb.append(text.charAt(i));
            } else {
                int nextIndex = i+1;
                while (nextIndex < text.length() && text.charAt(nextIndex) != '%') {
                    nextIndex++;
                }
                String key = text.substring(i+1, nextIndex);
                String replacement = replaceMap.get(key);
                sb.append(dfs(replaceMap, replacement, memo)); // dfs to replace deeper string(for replacement)

                i = nextIndex;
            }
        }
        memo.put(text, sb.toString());
        return memo.get(text);
    }
}

/**
T: O(t + n), n is number of "chars" replacement, t is Length of the original input text, 
because we walk through t chars, and replacement n chars
ex: abc_%B%
T: is abc_ + char number of (%B%) -> is 3 -> so totally is 4 + 3

S: O(n + s + r), n of replacement for map, s: recusion stack , r: StringBuilder result
 */

my first thought: it replace entire String, cant utilize memo, so it's slow.

class Solution {
    public String applySubstitutions(List<List<String>> replacements, String text) {
        Map<String, String> replaceMap = new HashMap<>();
        for (List<String> replacement : replacements) {
            replaceMap.put(replacement.get(0), replacement.get(1));
        }
        String[] result = new String[1];
        dfs(replaceMap, text, result);
        return result[0];
    }
    private void dfs(Map<String, String> replaceMap, String text, String[] result) {
        if (!text.contains("%")) {
            result[0] = text;
            return;
        }
        int index = text.indexOf("%");
        int nextIndex = index+1;
        while (nextIndex < text.length() && text.charAt(nextIndex) != '%') {
            nextIndex++;
        }
        String key = text.substring(index+1, nextIndex);
        String replacement = replaceMap.get(key);
        String newText = text.substring(0, index) + replacement + text.substring(nextIndex+1);
        
        dfs(replaceMap, newText, result);
    }
}