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).
1#include <unordered_map>
2#include <string>
3using namespace std;
4
5bool isIsomorphic(string s, string t) {
6 unordered_map<char, char> map_s, map_t;
7 for (int i = 0; i < s.length(); ++i) {
8 if (map_s.count(s[i]) != map_t.count(t[i])) || (map_s[s[i]] != map_t[t[i]]) {
9 return false;
10 }
11 map_s[s[i]] = t[i];
12 map_t[t[i]] = s[i];
13 }
14 return true;
15}We use two unordered maps to map characters from s to t and from t to s. As we iterate through each character, we verify that existing mappings are consistent, and update the maps as needed.
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.