Problem 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.

Intuition

The problem involves replacing placeholders in a given text with corresponding values from a mapping, where these values can themselves contain further placeholders. This recursive nature suggests an approach using depth-first search (DFS) to fully resolve all placeholders.

The solution involves a couple of key steps:

1. Mapping Storage: Use a hash table to store the mapping between placeholder names and their substitution values.

2. Recursive Replacement: Implement a recursive function (dfs) that searches for placeholders in the string. Each time it finds a placeholder, it extracts the key, looks up its value in the mapping, and replaces the placeholder with this value.

3. Complete Resolution: The recursion ensures that if a replacement itself contains placeholders, it will be further processed until no placeholders remain.

The main idea is to apply these substitutions until the text is entirely resolved without placeholders.

Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.

Solution Approach

To solve this problem, we utilize a hash table combined with recursion to efficiently handle and replace the placeholders in the given text string.

Here's a detailed walkthrough of the solution approach:

1. Hash Table for Mapping: We create a hash table d from the replacements, where each key-value pair corresponds to a placeholder and its replacement string. This enables quick lookups during the substitution process.

   d = {s: t for s, t in replacements}

2. Recursive Function (dfs): We define a recursive function dfs that processes the string s:

   • Find Placeholders: Locate the first occurrence of % to determine the start and end of a placeholder within the string.

     • Use s.find("%") to find the starting position i of a placeholder.
     • Use s.find("%", i + 1) to find the ending position j of the same placeholder.

   • Extract and Replace: Extract the key using the substring between these positions (s[i + 1 : j]). Recursively call dfs to resolve the replacement string, which accounts for further nested placeholders.

     key = s[i + 1 : j]
     replacement = dfs(d[key])

   • Combine Results: Construct the final string by concatenating the resolved portion before the placeholder, the resolved replacement, and calling dfs for the remaining part of the string after the placeholder.

     return s[:i] + replacement + dfs(s[j + 1 :])

3. Initiate Replacement: The main function applySubstitutions starts the recursive process with the initial text string to resolve all placeholders.

By iterating recursively and leveraging the mapping efficiently, this approach ensures that all nested and complex placeholders are accurately replaced, ultimately providing a fully substituted string.

Example Walkthrough

Let's illustrate the solution approach with a small example:

Imagine we have the replacements mapping as follows:

replacements = [
    ("name", "John"),
    ("greeting", "Hello, %name%"),
    ("farewell", "Goodbye, %name%")
]

And suppose we have a text string:

"%greeting%! How are you? %farewell%!"

Here's how the solution approach would work, step by step:

1. Hash Table Creation: We start by converting the replacements list into a hash table d for quick lookups:

   d = {
       "name": "John",
       "greeting": "Hello, %name%",
       "farewell": "Goodbye, %name%"
   }

2. Begin Recursive Replacement: We call the dfs function on the initial text string:

   • The first placeholder %greeting% is located in the string.
   • Inside dfs, we extract the key, which is greeting, and use it to retrieve the value "Hello, %name%" from d.

3. Nested Placeholder Resolution: The retrieved string "Hello, %name%" contains another placeholder %name%.

   • We recursively process %name% using dfs.
   • For %name%, the value "John" is obtained from d.

4. Combining Solutions: Once the innermost placeholder %name% is replaced with "John", the greeting part becomes "Hello, John".

   • We continue to resolve the rest of the original text by substituting %greeting% with "Hello, John", resulting in the intermediate outcome: "Hello, John! How are you? %farewell%!".

5. Resolve Remaining Placeholders: Next, we perform a similar process to replace %farewell%:

   • %farewell% is found to be "Goodbye, %name%".
   • Again, %name% resolves to "John", leading to "Goodbye, John".

6. Final Output: The fully substituted string after resolving all placeholders becomes:

   "Hello, John! How are you? Goodbye, John!"

Through this recursive process, every placeholder is iteratively resolved, ensuring the output string is free of any unresolved placeholders.

Solution Implementation

Time and Space Complexity

The code performs substitutions recursively using depth-first search (DFS):

1. Time Complexity:

   • There are three main operations contributing to the time complexity:
     1. Finding the next pair of % characters in s using s.find(), which takes O(n) time in the worst case.
     2. Constructing the dictionary d from the replacements list takes O(m), where m is the number of substitutions.
     3. Substituting the key in the string requires recursive calls. This involves traversing and replacing parts of the string, potentially visiting each character multiple times depending on the nested structure of substitutions.

   Therefore, the time complexity is O(m + n * L), where n is the length of the text string and L is the average length of the placeholder keys.

2. Space Complexity:

   • O(m) space for the dictionary d to store the substitutions.
   • O(n * L) space for the call stack due to recursion, which occurs due to potential nested placeholders.
   • O(n * L) space for building the resultant string as we might replace each %key% with its respective value from d.

   The overall space complexity is O(m + n * L).

Learn more about how to find time and space complexity quickly.