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).
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public bool IsIsomorphic(string s, string t) {
6 Dictionary<char, char> map_s = new Dictionary<char, char>();
7 Dictionary<char, char> map_t = new Dictionary<char, char>();
8
9 for (int i = 0; i < s.Length; i++) {
10 if ((map_s.ContainsKey(s[i]) && map_s[s[i]] != t[i]) ||
11 (map_t.ContainsKey(t[i]) && map_t[t[i]] != s[i]))
12 return false;
13
14 map_s[s[i]] = t[i];
15 map_t[t[i]] = s[i];
16 }
17 return true;
18 }
19}In C#, two dictionaries are utilized to establish mappings from s to t and t to s respectively. Any discrepancies in expected mappings during iteration result in a false return.
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.
1def
Construct a numerical pattern list for each string, marking character positions and checking for similar distributions across both pattern lists.