# 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>& mappings) { vector> isMapped(128, vector(128)); for (const vector& 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>& 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