Problem

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 makesub a substring ofs by replacing zero or more characters according tomappings. Otherwise, return false.

A substring is a contiguous non-empty sequence of characters within a string.

Examples

Example 1

1
2
3
4

Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
Output: true
Explanation: Replace the first 'e' in sub with '3' and 't' in sub with '7'.
Now sub = "l3e7" is a substring of s, so we return true.

Example 2

1
2
3
4

Input: s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
Output: false
Explanation: The string "f00l" is not a substring of s and no replacements can be made.
Note that we cannot replace '0' with 'o'.

Example 3

1
2
3
4

Input: s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
Output: true
Explanation: Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'.
Now sub = "l33tb" is a substring of s, so we return true.

Constraints

  • 1 <= sub.length <= s.length <= 5000
  • 0 <= mappings.length <= 1000
  • mappings[i].length == 2
  • oldi != newi
  • s and sub consist of uppercase and lowercase English letters and digits.
  • oldi and newi are either uppercase or lowercase English letters or digits.

Solution

Method 1 – Sliding Window with Replacement Mapping

Intuition

We want to check if sub can be transformed (using the allowed mappings) into any substring of s. For each window in s of length len(sub), we try to match sub to the window, allowing each character in sub to be replaced at most once according to the mapping. We use a mapping set for fast lookup.

Approach

  1. Build a set of allowed replacements from mappings for O(1) lookup.
  2. For each window of length len(sub) in s:
    • For each character in sub, check if it matches the corresponding character in s, or if it can be replaced (using the mapping) to match.
    • If all characters match for a window, return true.
  3. If no window matches, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        unordered_map<char, unordered_set<char>> mp;
        for (auto& m : mappings) mp[m[0]].insert(m[1]);
        int n = s.size(), m = sub.size();
        for (int i = 0; i + m <= n; ++i) {
            bool ok = true;
            for (int j = 0; j < m; ++j) {
                if (s[i+j] == sub[j]) continue;
                if (!mp.count(sub[j]) || !mp[sub[j]].count(s[i+j])) {
                    ok = false;
                    break;
                }
            }
            if (ok) return true;
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func matchReplacement(s string, sub string, mappings [][]byte) bool {
    mp := map[byte]map[byte]bool{}
    for _, m := range mappings {
        if mp[m[0]] == nil {
            mp[m[0]] = map[byte]bool{}
        }
        mp[m[0]][m[1]] = true
    }
    n, mlen := len(s), len(sub)
    for i := 0; i+mlen <= n; i++ {
        ok := true
        for j := 0; j < mlen; j++ {
            if s[i+j] == sub[j] {
                continue
            }
            if mp[sub[j]] == nil || !mp[sub[j]][s[i+j]] {
                ok = false
                break
            }
        }
        if ok {
            return true
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public boolean matchReplacement(String s, String sub, char[][] mappings) {
        Map<Character, Set<Character>> mp = new HashMap<>();
        for (char[] m : mappings) {
            mp.computeIfAbsent(m[0], k -> new HashSet<>()).add(m[1]);
        }
        int n = s.length(), m = sub.length();
        for (int i = 0; i + m <= n; i++) {
            boolean ok = true;
            for (int j = 0; j < m; j++) {
                if (s.charAt(i+j) == sub.charAt(j)) continue;
                if (!mp.containsKey(sub.charAt(j)) || !mp.get(sub.charAt(j)).contains(s.charAt(i+j))) {
                    ok = false;
                    break;
                }
            }
            if (ok) return true;
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun matchReplacement(s: String, sub: String, mappings: Array<CharArray>): Boolean {
        val mp = mutableMapOf<Char, MutableSet<Char>>()
        for (m in mappings) mp.getOrPut(m[0]) { mutableSetOf() }.add(m[1])
        val n = s.length
        val mlen = sub.length
        for (i in 0..n-mlen) {
            var ok = true
            for (j in 0 until mlen) {
                if (s[i+j] == sub[j]) continue
                if (!mp.containsKey(sub[j]) || !mp[sub[j]]!!.contains(s[i+j])) {
                    ok = false
                    break
                }
            }
            if (ok) return true
        }
        return false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: list[list[str]]) -> bool:
        mp = {a: set() for a, _ in mappings}
        for a, b in mappings:
            mp[a].add(b)
        n, m = len(s), len(sub)
        for i in range(n - m + 1):
            ok = True
            for j in range(m):
                if s[i+j] == sub[j]:
                    continue
                if sub[j] not in mp or s[i+j] not in mp[sub[j]]:
                    ok = False
                    break
            if ok:
                return True
        return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

impl Solution {
    pub fn match_replacement(s: String, sub: String, mappings: Vec<Vec<char>>) -> bool {
        use std::collections::{HashMap, HashSet};
        let mut mp: HashMap<char, HashSet<char>> = HashMap::new();
        for m in mappings {
            mp.entry(m[0]).or_default().insert(m[1]);
        }
        let n = s.len();
        let m = sub.len();
        let s_chars: Vec<char> = s.chars().collect();
        let sub_chars: Vec<char> = sub.chars().collect();
        for i in 0..=n-m {
            let mut ok = true;
            for j in 0..m {
                if s_chars[i+j] == sub_chars[j] {
                    continue;
                }
                if !mp.get(&sub_chars[j]).map_or(false, |set| set.contains(&s_chars[i+j])) {
                    ok = false;
                    break;
                }
            }
            if ok {
                return true;
            }
        }
        false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    matchReplacement(s: string, sub: string, mappings: string[][]): boolean {
        const mp = new Map<string, Set<string>>();
        for (const [a, b] of mappings) {
            if (!mp.has(a)) mp.set(a, new Set());
            mp.get(a)!.add(b);
        }
        const n = s.length, m = sub.length;
        for (let i = 0; i + m <= n; i++) {
            let ok = true;
            for (let j = 0; j < m; j++) {
                if (s[i+j] === sub[j]) continue;
                if (!mp.has(sub[j]) || !mp.get(sub[j])!.has(s[i+j])) {
                    ok = false;
                    break;
                }
            }
            if (ok) return true;
        }
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(n*m), where n is the length of s and m is the length of sub, as we check every window.
  • 🧺 Space complexity: O(k), where k is the number of mappings, for the mapping set.