Skip to content

2301. Match Substring After Replacement 👍

  • Time: $O(|\texttt{s}||\texttt{sub}|)$
  • Space: $O(128)^2 = O(1)$
 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
30
31
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)
      isMapped[m[0]][m[1]] = 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];        // sub's char
      const char b = s[start + i];  // s' char
      if (a != b && !isMapped[a][b])
        return false;
    }

    return true;
  }
};

 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
class Solution {
  public boolean matchReplacement(String s, String sub, char[][] mappings) {
    boolean[][] isMapped = new boolean[128][128];

    for (char[] m : mappings)
      isMapped[m[0]][m[1]] = 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);       // sub's char
      final char b = s.charAt(start + i); // s' char
      if (a != b && !isMapped[a][b])
        return false;
    }

    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]        # sub's char
      b = s[start + i]  # s' char
      if a != b and not isMapped[ord(a)][ord(b)]:
        return False

    return True