Question

2301. Match Substring After Replacement

中文文档

Description

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.

Solutions

Solution 1: Hash Table + Enumeration

First, we use a hash table $d$ to record the set of characters that each character can be replaced with.

Then we enumerate all substrings of length $sub$ in $s$, and judge whether the string $sub$ can be obtained by replacement. If it can, return true, otherwise enumerate the next substring.

At the end of the enumeration, it means that $sub$ cannot be obtained by replacing any substring in $s$, so return false.

The time complexity is $O(m \times n)$, and the space complexity is $O(C^2)$. Here, $m$ and $n$ are the lengths of the strings $s$ and $sub$ respectively, and $C$ is the size of the character set.

class Solution:
  def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
    d = defaultdict(set)
    for a, b in mappings:
      d[a].add(b)
    for i in range(len(s) - len(sub) + 1):
      if all(a == b or a in d[b] for a, b in zip(s[i : i + len(sub)], sub)):
        return True
    return False

class Solution {
  public boolean matchReplacement(String s, String sub, char[][] mappings) {
    Map<Character, Set<Character>> d = new HashMap<>();
    for (var e : mappings) {
      d.computeIfAbsent(e[0], k -> new HashSet<>()).add(e[1]);
    }
    int m = s.length(), n = sub.length();
    for (int i = 0; i < m - n + 1; ++i) {
      boolean ok = true;
      for (int j = 0; j < n && ok; ++j) {
        char a = s.charAt(i + j), b = sub.charAt(j);
        if (a != b && !d.getOrDefault(b, Collections.emptySet()).contains(a)) {
          ok = false;
        }
      }
      if (ok) {
        return true;
      }
    }
    return false;
  }
}

class Solution {
public:
  bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
    unordered_map<char, unordered_set<char>> d;
    for (auto& e : mappings) {
      d[e[0]].insert(e[1]);
    }
    int m = s.size(), n = sub.size();
    for (int i = 0; i < m - n + 1; ++i) {
      bool ok = true;
      for (int j = 0; j < n && ok; ++j) {
        char a = s[i + j], b = sub[j];
        if (a != b && !d[b].count(a)) {
          ok = false;
        }
      }
      if (ok) {
        return true;
      }
    }
    return false;
  }
};

func matchReplacement(s string, sub string, mappings [][]byte) bool {
  d := map[byte]map[byte]bool{}
  for _, e := range mappings {
    if d[e[0]] == nil {
      d[e[0]] = map[byte]bool{}
    }
    d[e[0]][e[1]] = true
  }
  for i := 0; i < len(s)-len(sub)+1; i++ {
    ok := true
    for j := 0; j < len(sub) && ok; j++ {
      a, b := s[i+j], sub[j]
      if a != b && !d[b][a] {
        ok = false
      }
    }
    if ok {
      return true
    }
  }
  return false
}

Solution 2: Array + Enumeration

Since the character set only contains uppercase and lowercase English letters and numbers, we can directly use a $128 \times 128$ array $d$ to record the set of characters that each character can be replaced with.

The time complexity is $O(m \times n)$, and the space complexity is $O(C^2)$.

class Solution:
  def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
    d = [[False] * 128 for _ in range(128)]
    for a, b in mappings:
      d[ord(a)][ord(b)] = True
    for i in range(len(s) - len(sub) + 1):
      if all(
        a == b or d[ord(b)][ord(a)] for a, b in zip(s[i : i + len(sub)], sub)
      ):
        return True
    return False

class Solution {
  public boolean matchReplacement(String s, String sub, char[][] mappings) {
    boolean[][] d = new boolean[128][128];
    for (var e : mappings) {
      d[e[0]][e[1]] = true;
    }
    int m = s.length(), n = sub.length();
    for (int i = 0; i < m - n + 1; ++i) {
      boolean ok = true;
      for (int j = 0; j < n && ok; ++j) {
        char a = s.charAt(i + j), b = sub.charAt(j);
        if (a != b && !d[b][a]) {
          ok = false;
        }
      }
      if (ok) {
        return true;
      }
    }
    return false;
  }
}

class Solution {
public:
  bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
    bool d[128][128]{};
    for (auto& e : mappings) {
      d[e[0]][e[1]] = true;
    }
    int m = s.size(), n = sub.size();
    for (int i = 0; i < m - n + 1; ++i) {
      bool ok = true;
      for (int j = 0; j < n && ok; ++j) {
        char a = s[i + j], b = sub[j];
        if (a != b && !d[b][a]) {
          ok = false;
        }
      }
      if (ok) {
        return true;
      }
    }
    return false;
  }
};

func matchReplacement(s string, sub string, mappings [][]byte) bool {
  d := [128][128]bool{}
  for _, e := range mappings {
    d[e[0]][e[1]] = true
  }
  for i := 0; i < len(s)-len(sub)+1; i++ {
    ok := true
    for j := 0; j < len(sub) && ok; j++ {
      a, b := s[i+j], sub[j]
      if a != b && !d[b][a] {
        ok = false
      }
    }
    if ok {
      return true
    }
  }
  return false
}