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:
"A" with "abc" and "B" with "def".%A% with "abc" and %B% with "def" in the text."abc_def".Example 2:
Input: replacements = [["A","bce"],["B","ace"],["C","abc%B%"]], text = "%A%_%B%_%C%"
Output: "bce_ace_abcace"
Explanation:
"A" with "bce", "B" with "ace", and "C" with "abc%B%".%A% with "bce" and %B% with "ace" in the text.%C%, substitute %B% in "abc%B%" with "ace" to obtain "abcace"."bce_ace_abcace".
Constraints:
1 <= replacements.length <= 10replacements 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>%.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 - 1text or in any replacement value corresponds to a key in the replacements mapping.We use a hash table d to store the substitution mapping, and then define a function dfs to recursively replace the placeholders in the string.
The execution logic of the function dfs is as follows:
i of the first placeholder in the string s. If not found, return s;j of the first placeholder in the string s. If not found, return s;d[key];In the main function, we call the dfs function, pass in the text string 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.
Java
C++
Go
TypeScript
Practice Apply Substitutions with our built-in code editor and test cases.
Practice on FleetCode