1. Isomorphic Strings (LeetCode)
Model answer
The task
Determine whether two strings have the same length and whether their characters can be matched one-to-one so that each position in one string corresponds to the same position in the other.
Key idea
Maintain mappings in both directions. A character in the first string must always map to the same character in the second, and two different characters cannot map to the same character.
Approach
- Return
Falseif the strings have different lengths. - Create a mapping from the first string to the second.
- Create a reverse mapping from the second string to the first.
- Scan corresponding characters together.
- If either mapping conflicts with the current pair, return
False; otherwise, record the pair. - If every pair is consistent, return
True.
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
forward = {}
reverse = {}
for left, right in zip(s, t):
if left in forward and forward[left] != right:
return False
if right in reverse and reverse[right] != left:
return False
forward[left] = right
reverse[right] = left
return True
Complexity:
- Time: O(n), where n is the string length; each position is checked once.
- Space: O(k), where k is the number of distinct characters stored in the mappings.
Common follow-ups
- What if the mapping only needs to preserve characters in one direction? Use just one mapping; this does not enforce a one-to-one correspondence.
- What if the strings are streamed? Process corresponding characters as they arrive, retaining the two mappings.
- Can the extra space be bounded for a fixed alphabet? Yes; use arrays instead of dictionaries when the character set has a known, small range.