Skip to content

Latest commit

 

History

History

2301

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

2301. Match Substring After Replacement (Hard)

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.

 

Example 1:

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:

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:

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.

Companies: Discord

Related Topics:
Array, Hash Table, String, String Matching

Similar Questions:

Hints:

  • Enumerate all substrings of s with the same length as sub, and compare each substring to sub for equality.
  • How can you quickly tell if a character of s can result from replacing the corresponding character in sub?

Solution 1.

Generate all the substrings of s that have the same length as sub. Check if any one of them can be generated via sub.

// OJ: https://leetcode.com/problems/match-substring-after-replacement
// Author: github.com/lzl124631x
// Time: O(MN + K) where `M` is the length of `s`, `N` is the length of `sub`, and `K` is the size of `mappings`
// Space: O(K)
class Solution {
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        unordered_map<char, unordered_set<char>> m;
        int M = s.size(), N = sub.size();
        for (auto &p : mappings) m[p[0]].insert(p[1]);
        for (int i = 0; i + N <= M; ++i) {
            int j = 0;
            for (; j < N; ++j) {
                if (s[i + j] == sub[j] || (m.count(sub[j]) && m[sub[j]].count(s[i + j]))) continue;
                break;
            }
            if (j == N) return true;
        }
        return false;
    }
};