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
- Build a map from key to its raw replacement string.
- Write a recursive expander with memoisation: to expand a key, scan its replacement text and recursively expand any
%X%placeholders it contains. - Memoising per key avoids exponential blow-up when the same key is referenced many times.
- Then expand the top-level
textthe 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.