2301. Match Substring After Replacement Hard

1/**
2 * [2301] Match Substring After Replacement
3 *
4 * 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 replace any number of oldi characters of sub with newi. Each character in sub cannot be replaced more than once.
5 * 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.
6 * A substring is a contiguous non-empty sequence of characters within a string.
7 *  
8 * Example 1:
9 *
10 * Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
11 * Output: true
12 * Explanation: Replace the first 'e' in sub with '3' and 't' in sub with '7'.
13 * Now sub = "l3e7" is a substring of s, so we return true.
14 * Example 2:
15 *
16 * Input: s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
17 * Output: false
18 * Explanation: The string "f00l" is not a substring of s and no replacements can be made.
19 * Note that we cannot replace '0' with 'o'.
20 *
21 * Example 3:
22 *
23 * Input: s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
24 * Output: true
25 * Explanation: Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'.
26 * Now sub = "l33tb" is a substring of s, so we return true.
27 *
28 *  
29 * Constraints:
30 *
31 * 1 <= sub.length <= s.length <= 5000
32 * 0 <= mappings.length <= 1000
33 * mappings[i].length == 2
34 * oldi != newi
35 * s and sub consist of uppercase and lowercase English letters and digits.
36 * oldi and newi are either uppercase or lowercase English letters or digits.
37 *
38 */
39pub struct Solution {}
40use std::collections::HashMap;
41use std::collections::HashSet;
42// problem: https://leetcode.com/problems/match-substring-after-replacement/
43// discuss: https://leetcode.com/problems/match-substring-after-replacement/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn match_replacement(s: String, sub: String, mappings: Vec<Vec<char>>) -> bool {
49        if sub.len() > s.len() {
50            return false;
51        }
52        let mut better_map: HashMap<char, HashSet<char>> = HashMap::new();
53        for v in mappings {
54            better_map
55                .entry(v[0])
56                .and_modify(|x| {
57                    x.insert(v[1]);
58                })
59                .or_insert(vec![v[1]].iter().cloned().collect());
60        }
61
62        let l = sub.len();
63        let chs: Vec<char> = s.chars().collect();
64        for i in 0..s.len() - l + 1 {
65            let mut good = true;
66            for (j, v) in sub.chars().enumerate() {
67                if v != chs[i + j] && !better_map.entry(v).or_default().contains(&chs[i + j]) {
68                    good = false;
69                    break;
70                }
71            }
72            if good {
73                return good;
74            }
75        }
76        false
77    }
78}
79
80// submission codes end
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_2301() {
88        assert_eq!(
89            Solution::match_replacement(
90                "fool3e7bar".to_string(),
91                "leet".to_string(),
92                vec![vec!['e', '3'], vec!['t', '7'], vec!['t', '8']]
93            ),
94            true
95        );
96    }
97
98    #[test]
99    fn test_2301_1() {
100        assert_eq!(
101            Solution::match_replacement(
102                "rrrrlrrrrlrrrrr".to_string(),
103                "rrrrr".to_string(),
104                vec![]
105            ),
106            true
107        );
108    }
109}
110