⚡Flashcard Drill➔
NeetCode #161LC-3481MediumArrays & Hashing
← Back to All Problems

#161 · #3481 · Apply Substitutions(应用替换)

📌 Problem Statement & Constraints

You are given replacements, a list of [key, value] pairs where each key is a single uppercase letter and the value may contain placeholders of the form %X%. Given a text containing such placeholders, expand every placeholder recursively and return the resulting string. Constraints: 1 <= replacements.length <= 26; all keys are distinct; substitutions are guaranteed to terminate.

💡 Core Algorithmic Approaches

  1. Build a map from key to its raw replacement string.
  2. Write a recursive expander with memoisation: to expand a key, scan its replacement text and recursively expand any %X% placeholders it contains.
  3. Memoising per key avoids exponential blow-up when the same key is referenced many times.
  4. Then expand the top-level text the same way. The guarantee that substitutions terminate means the recursion has no cycles.

💻 Benchmark Python3 Implementation

class Solution:
    def applySubstitutions(self, replacements: List[List[str]], text: str) -> str:
        mp = {k: v for k, v in replacements}
        memo = {}

        def expand(ch: str) -> str:
            if ch in memo:
                return memo[ch]
            s = mp.get(ch, ch)
            out = []
            i = 0
            while i < len(s):
                if s[i] == "%":            # placeholder %X%
                    j = s.index("%", i + 1)
                    out.append(expand(s[i + 1:j]))
                    i = j + 1
                else:
                    out.append(s[i])
                    i += 1
            memo[ch] = "".join(out)
            return memo[ch]

        res = []
        i = 0
        while i < len(text):
            if text[i] == "%":
                j = text.index("%", i + 1)
                res.append(expand(text[i + 1:j]))
                i = j + 1
            else:
                res.append(text[i])
                i += 1
        return "".join(res)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total expanded length): with memoisation each key is expanded once and its result reused.
💾 Space Complexity
O(total expanded length) for the memo table.

⚠️ Interview Pitfalls & Follow-ups

  • Expanding iteratively without memoisation: nested references cause exponential repeated work.
  • Ignoring nesting: a replacement value may itself contain placeholders, so expansion must be recursive.
  • Scanning for the closing % incorrectly: s.index("%", i + 1) finds the matching delimiter; assuming a fixed width would fail.
  • Worrying about cycles: the problem guarantees the substitutions terminate, so no cycle detection is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems