We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Apply Substitutions

Number: 3825

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a mapping from single uppercase letter keys to string values (which may themselves contain placeholders in the form %X%), and a text string composed solely of these placeholders separated by underscores, substitute each placeholder with its fully expanded string value. The expanded value is obtained by recursively replacing any nested placeholders, ensuring that the final answer contains no placeholders.

Key Insights

  • Use a dictionary (or hash map) to store the mapping from key to value.
  • The replacement values may contain nested placeholders, requiring a recursive (or DFS) approach to fully expand each key.
  • No cyclic dependencies exist, guaranteeing termination.
  • Use memoization to avoid redundant computations while expanding each placeholder.

Space and Time Complexity

Time Complexity: O(N) where N is the total number of characters in the text and all replacement strings combined, since each character is processed a constant number of times. Space Complexity: O(N) due to the storage required for recursion, memoization, and the final expanded strings.

Solution

The main idea is to first convert the list of replacement pairs into a dictionary mapping keys to their replacement strings. Then, use a depth-first search (DFS) with memoization to recursively expand each key’s value by searching for placeholders using a regular expression pattern.

  1. For each key, if its expanded value is already computed (stored in a memo dictionary), return it immediately.
  2. Otherwise, scan its value for any placeholders of the form %X% and recursively replace them with their expanded versions.
  3. After processing all replacements, substitute the placeholders in the main text similarly by applying the DFS expansion. This approach guarantees that each placeholder is expanded fully and only once.

Code Solutions

# Python solution with line-by-line comments

def applySubstitutions(replacements, text):
    # Create a dictionary to map each key to its string value.
    mapping = { key: value for key, value in replacements }
    # Memoization dictionary to store already expanded keys.
    memo = {}
    
    import re
    # Regex pattern to find placeholders, e.g., %A%, %B%, etc.
    pattern = re.compile(r'%([A-Z])%')
    
    def dfs(key):
        # If the key's expanded value is already computed, return it.
        if key in memo:
            return memo[key]
        # Retrieve the raw replacement value for the key.
        raw_value = mapping[key]
        
        # Function to replace a placeholder in the raw_value.
        def replace_placeholder(match):
            inner_key = match.group(1)  # Extract the key from the placeholder.
            return dfs(inner_key)       # Recursively expand the inner key.
        
        # Use regex substitution to replace all placeholders with their expanded values.
        expanded_value = pattern.sub(replace_placeholder, raw_value)
        # Memoize the computed expanded string.
        memo[key] = expanded_value
        return expanded_value
    
    # Replace placeholders in the main text by using the dfs helper.
    final_text = pattern.sub(lambda m: dfs(m.group(1)), text)
    return final_text

# Example usage:
replacements = [["A","bce"],["B","ace"],["C","abc%B%"]]
text = "%A%_%B%_%C%"
print(applySubstitutions(replacements, text))  # Output: "bce_ace_abcace"
← Back to All Questions