Match substring after replacement

Array Hash Table String String Matching

43.2% acceptance

Feb 25, 2026

393

You are given two strings s and sub. You are also given a 2D character array mappings where mappings[i] = [oldi, newi] indicates that you may perform the following operation any number of times: Replace a character oldi of sub with newi. Each character in sub cannot be replaced more than once. Return true if it is possible to make sub a substring of s by replacing zero or more characters according to mappings. Otherwise, return false. A substring is a contiguous non-empty sequence of characters within a string.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashSet;


impl Solution {
  pub fn match_replacement(s: String, sub: String, mappings: Vec<Vec<char>>) -> bool {
    let mut allowed: std::collections::HashMap<char, HashSet<char>> = std::collections::HashMap::new();
    for m in &mappings {
      allowed.entry(m[0]).or_default().insert(m[1]);
    }
    let s: Vec<char> = s.chars().collect();
    let sub: Vec<char> = sub.chars().collect();
    let n = s.len();
    let m = sub.len();
    if m > n { return false; }
    'outer: for i in 0..=(n - m) {
      for j in 0..m {
        if s[i + j] != sub[j] && !allowed.get(&sub[j]).map_or(false, |set| set.contains(&s[i + j])) {
          continue 'outer;
        }
      }
      return true;
    }
    false
  }
}