Sponsored
Sponsored
This approach involves using two hash maps (or dictionaries) to track the character mappings from string s to string t and vice versa. We iterate over the characters of both strings and update the mappings. If at any point the expected character mapping does not match, we conclude that the strings are not isomorphic.
Time Complexity: O(n) where n is the length of the strings (which are equal).
Space Complexity: O(1), as the size of the map is constant (256 character ASCII set).
1def isIsomorphic(s, t):
2 map_s, map_t = {}, {}
3 for cs, ct in zip(s, t):
4 if map_s.get(cs, ct) != ct or map_t.get(ct, cs) != cs:
5 return False
6 map_s[cs] = ct
7 map_t[ct] = cs
8 return TrueWe create two dictionaries to check and store character mappings between strings s and t. During each comparison, consistency is checked, ensuring a valid bidirectional mapping is followed.
Generate a unique pattern for each string by numbering the characters according to their first appearance. Compare character patterns of the two strings. If the patterns match, the strings are isomorphic.
Time Complexity: O(n), due to single-pass traversal for number pattern generation.
Space Complexity: O(1), as the pattern size remains constant with 256 ASCII values.
1#
Generate a number pattern for each string based on character occurrences using a mapping array. Compare these patterns; identical patterns indicate that the strings are isomorphic.