Apply substitutions

Array Hash Table String Depth-First Search Breadth-First Search Graph Theory Topological Sort

77.4% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn apply_substitutions(replacements: Vec<Vec<String>>, text: String) -> String {
    let mut map: HashMap<String, String> = HashMap::new();
    for r in &replacements {
      map.insert(r[0].clone(), r[1].clone());
    }
    // Resolve all replacements (memoized)
    let keys: Vec<String> = map.keys().cloned().collect();
    let mut resolved: HashMap<String, String> = HashMap::new();
    for key in &keys {
      if !resolved.contains_key(key) {
        Self::resolve(key, &map, &mut resolved);
      }
    }
    Self::substitute(&text, &resolved)
  }

  fn resolve(key: &str, map: &HashMap<String, String>, resolved: &mut HashMap<String, String>) {
    if resolved.contains_key(key) { return; }
    let val = map.get(key).cloned().unwrap_or_default();
    // Find all %var% in val and resolve them first
    let substituted = Self::substitute_with_resolve(&val, map, resolved);
    resolved.insert(key.to_string(), substituted);
  }

  fn substitute_with_resolve(s: &str, map: &HashMap<String, String>, resolved: &mut HashMap<String, String>) -> String {
    let mut result = String::new();
    let bytes = s.as_bytes();
    let mut i = 0;
    while i < bytes.len() {
      if bytes[i] == b'%' {
        if let Some(j) = s[i+1..].find('%') {
          let var = &s[i+1..i+1+j];
          if map.contains_key(var) {
            if !resolved.contains_key(var) {
              Self::resolve(var, map, resolved);
            }
            result.push_str(resolved.get(var).unwrap());
            i = i + 1 + j + 1;
            continue;
          }
        }
      }
      result.push(bytes[i] as char);
      i += 1;
    }
    result
  }

  fn substitute(s: &str, resolved: &HashMap<String, String>) -> String {
    let mut result = String::new();
    let bytes = s.as_bytes();
    let mut i = 0;
    while i < bytes.len() {
      if bytes[i] == b'%' {
        if let Some(j) = s[i+1..].find('%') {
          let var = &s[i+1..i+1+j];
          if let Some(val) = resolved.get(var) {
            result.push_str(val);
            i = i + 1 + j + 1;
            continue;
          }
        }
      }
      result.push(bytes[i] as char);
      i += 1;
    }
    result
  }
}