Two strings s and t of the same length are isomorphic if you can rename the characters of s to get t. Every occurrence of a character must be renamed to the same character, and two different characters may not be renamed to the same one (a character may map to itself). Return true if s and t are isomorphic.
- 1 <= s.length <= 5 * 10^4
- t.length == s.length
- `s` and `t` contain any valid ASCII characters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force could try to compare the "pattern" of each pair of positions, which is O(n^2). The real requirement is that the character mapping is a bijection. Walk both strings together. At position i, if s[i] already has a partner it must be t[i], and if t[i] already has a partner it must be s[i]. Two maps (or two arrays of size 256) check both directions in O(1) per character.
Algorithm
- Create two arrays of size 256:
sToTandtToS, filled with a "no mapping" marker. - For each index
i, reada = s[i]andb = t[i]. - If
ais mapped to something other thanb, orbis mapped to something other thana, return false. - Otherwise record
sToT[a] = bandtToS[b] = a. - After the loop, return true.
O(n)Space: O(1), the arrays have a fixed size of 256s = "badc", t = "baba". Always test the reverse mapping too.class Solution: def isIsomorphic(self, s: str, t: str) -> bool: s_to_t = {} t_to_s = {} for a, b in zip(s, t): if a in s_to_t and s_to_t[a] != b: return False # a already maps elsewhere if b in t_to_s and t_to_s[b] != a: return False # b already taken by another character s_to_t[a] = b t_to_s[b] = a return True