3481. Apply Substitutions 🔒

Description

You are given a replacements mapping and a text string that may contain placeholders formatted as %var%, where each var corresponds to a key in the replacements mapping. Each replacement value may itself contain one or more such placeholders. Each placeholder is replaced by the value associated with its corresponding replacement key.

Return the fully substituted text string which does not contain any placeholders.

Example 1:

Input: replacements = [["A","abc"],["B","def"]], text = "%A%_%B%"

Output: "abc_def"

Explanation:

The mapping associates "A" with "abc" and "B" with "def".
Replace %A% with "abc" and %B% with "def" in the text.
The final text becomes "abc_def".

Example 2:

Input: replacements = [["A","bce"],["B","ace"],["C","abc%B%"]], text = "%A%_%B%_%C%"

Output: "bce_ace_abcace"

Explanation:

The mapping associates "A" with "bce", "B" with "ace", and "C" with "abc%B%".
Replace %A% with "bce" and %B% with "ace" in the text.
Then, for %C%, substitute %B% in "abc%B%" with "ace" to obtain "abcace".
The final text becomes "bce_ace_abcace".

Constraints:

1 <= replacements.length <= 10
Each element of replacements is a two-element list [key, value], where:
- key is a single uppercase English letter.
- value is a non-empty string of at most 8 characters that may contain zero or more placeholders formatted as %<key>%.
All replacement keys are unique.
The text string is formed by concatenating all key placeholders (formatted as %<key>%) randomly from the replacements mapping, separated by underscores.
text.length == 4 * replacements.length - 1
Every placeholder in the text or in any replacement value corresponds to a key in the replacements mapping.
There are no cyclic dependencies between replacement keys.

Solutions

Solution 1: Hash Table + Recursion

We use a hash table \(\textit{d}\) to store the substitution mapping, and then define a function \(\textit{dfs}\) to recursively replace the placeholders in the string.

The execution logic of the function \(\textit{dfs}\) is as follows:

Find the starting position \(i\) of the first placeholder in the string \(\textit{s}\). If not found, return \(\textit{s}\);
Find the ending position \(j\) of the first placeholder in the string \(\textit{s}\). If not found, return \(\textit{s}\);
Extract the key of the placeholder, and then recursively replace the value of the placeholder \(d[key]\);
Return the replaced string.

In the main function, we call the \(\textit{dfs}\) function, pass in the text string \(\textit{text}\), and return the result.

The time complexity is \(O(m + n \times L)\), and the space complexity is \(O(m + n \times L)\). Where \(m\) is the length of the substitution mapping, and \(n\) and \(L\) are the length of the text string and the average length of the placeholders, respectively.

Python3JavaC++GoTypeScript

class Solution:
    def applySubstitutions(self, replacements: List[List[str]], text: str) -> str:
        def dfs(s: str) -> str:
            i = s.find("%")
            if i == -1:
                return s
            j = s.find("%", i + 1)
            if j == -1:
                return s
            key = s[i + 1 : j]
            replacement = dfs(d[key])
            return s[:i] + replacement + dfs(s[j + 1 :])

        d = {s: t for s, t in replacements}
        return dfs(text)

class Solution {
    private final Map<String, String> d = new HashMap<>();

    public String applySubstitutions(List<List<String>> replacements, String text) {
        for (List<String> e : replacements) {
            d.put(e.get(0), e.get(1));
        }
        return dfs(text);
    }

    private String dfs(String s) {
        int i = s.indexOf("%");
        if (i == -1) {
            return s;
        }
        int j = s.indexOf("%", i + 1);
        if (j == -1) {
            return s;
        }
        String key = s.substring(i + 1, j);
        String replacement = dfs(d.getOrDefault(key, ""));
        return s.substring(0, i) + replacement + dfs(s.substring(j + 1));
    }
}

class Solution {
public:
    string applySubstitutions(vector<vector<string>>& replacements, string text) {
        unordered_map<string, string> d;
        for (const auto& e : replacements) {
            d[e[0]] = e[1];
        }
        auto dfs = [&](this auto&& dfs, const string& s) -> string {
            size_t i = s.find('%');
            if (i == string::npos) {
                return s;
            }
            size_t j = s.find('%', i + 1);
            if (j == string::npos) {
                return s;
            }
            string key = s.substr(i + 1, j - i - 1);
            string replacement = dfs(d[key]);
            return s.substr(0, i) + replacement + dfs(s.substr(j + 1));
        };
        return dfs(text);
    }
};

func applySubstitutions(replacements [][]string, text string) string {
    d := make(map[string]string)
    for _, e := range replacements {
        d[e[0]] = e[1]
    }
    var dfs func(string) string
    dfs = func(s string) string {
        i := strings.Index(s, "%")
        if i == -1 {
            return s
        }
        j := strings.Index(s[i+1:], "%")
        if j == -1 {
            return s
        }
        j += i + 1
        key := s[i+1 : j]
        replacement := dfs(d[key])
        return s[:i] + replacement + dfs(s[j+1:])
    }

    return dfs(text)
}

function applySubstitutions(replacements: string[][], text: string): string {
    const d: Record<string, string> = {};
    for (const [key, value] of replacements) {
        d[key] = value;
    }

    const dfs = (s: string): string => {
        const i = s.indexOf('%');
        if (i === -1) {
            return s;
        }
        const j = s.indexOf('%', i + 1);
        if (j === -1) {
            return s;
        }
        const key = s.slice(i + 1, j);
        const replacement = dfs(d[key] ?? '');
        return s.slice(0, i) + replacement + dfs(s.slice(j + 1));
    };

    return dfs(text);
}

3481. Apply Substitutions 🔒

Description

Solutions

Solution 1: Hash Table + Recursion

Comments