2301. Match Substring After Replacement LeetCode Solution

In this guide, you will get 2301. Match Substring After Replacement LeetCode Solution with the best time and space complexity. The solution to Match Substring After Replacement problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Match Substring After Replacement solution in C++
4. Match Substring After Replacement solution in Java
5. Match Substring After Replacement solution in Python
6. Additional Resources

Problem Statement of Match Substring After Replacement

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.

Complexity Analysis

• Time Complexity: O(|\texttt{s}||\texttt{sub}|)
• Space Complexity: O(128)^2 = O(1)

2301. Match Substring After Replacement LeetCode Solution in C++

class Solution {
 public:
  bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
    vector<vector<bool>> isMapped(128, vector<bool>(128));

    for (const vector<char>& m : mappings) {
      const char old = m[0];
      const char _new = m[1];
      isMapped[old][_new] = true;
    }

    for (int i = 0; i < s.length(); ++i)
      if (canTransform(s, i, sub, isMapped))
        return true;

    return false;
  }

 private:
  bool canTransform(const string& s, int start, const string& sub,
                    const vector<vector<bool>>& isMapped) {
    if (start + sub.length() > s.length())
      return false;

    for (int i = 0; i < sub.length(); ++i) {
      const char a = sub[i];
      const char b = s[start + i];
      if (a != b && !isMapped[a][b])
        return false;
    }

    return true;
  }
};
/* code provided by PROGIEZ */

2301. Match Substring After Replacement LeetCode Solution in Java

class Solution {
  public boolean matchReplacement(String s, String sub, char[][] mappings) {
    boolean[][] isMapped = new boolean[128][128];

    for (char[] m : mappings) {
      final char old = m[0];
      final char _new = m[1];
      isMapped[old][_new] = true;
    }

    for (int i = 0; i < s.length(); ++i)
      if (canTransform(s, i, sub, isMapped))
        return true;

    return false;
  }

  private boolean canTransform(final String s, int start, final String sub, boolean[][] isMapped) {
    if (start + sub.length() > s.length())
      return false;

    for (int i = 0; i < sub.length(); ++i) {
      final char a = sub.charAt(i);
      final char b = s.charAt(start + i);
      if (a != b && !isMapped[a][b])
        return false;
    }

    return true;
  }
}
// code provided by PROGIEZ

2301. Match Substring After Replacement LeetCode Solution in Python

class Solution:
  def matchReplacement(
      self,
      s: str,
      sub: str,
      mappings: list[list[str]],
  ) -> bool:
    isMapped = [[False] * 128 for _ in range(128)]

    for old, new in mappings:
      isMapped[ord(old)][ord(new)] = True

    for i in range(len(s)):
      if self._canTransform(s, i, sub, isMapped):
        return True

    return False

  def _canTransform(
      self,
      s: str,
      start: int,
      sub: str,
      isMapped: list[list[bool]],
  ) -> bool:
    if start + len(sub) > len(s):
      return False

    for i in range(len(sub)):
      a = sub[i]
      b = s[start + i]
      if a != b and not isMapped[ord(a)][ord(b)]:
        return False

    return True
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.