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).
1import java.util.HashMap;
2
3public class IsomorphicStrings {
4 public boolean isIsomorphic(String s, String t) {
5 HashMap<Character, Character> map_s = new HashMap<>();
6 HashMap<Character, Character> map_t = new HashMap<>();
7 for (int i = 0; i < s.length(); ++i) {
8 char sc = s.charAt(i);
9 char tc = t.charAt(i);
10 if (map_s.containsKey(sc) && map_s.get(sc) != tc ||
11 map_t.containsKey(tc) && map_t.get(tc) != sc)
12 return false;
13 map_s.put(sc, tc);
14 map_t.put(tc, sc);
15 }
16 return true;
17 }
18}
Two hash maps are used to store character mappings from s to t and vice versa. We check for consistent mappings and return false if any inconsistency is found.
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.
1using System;
using System.Collections.Generic;
public class Solution {
private List<int> GeneratePattern(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();
List<int> pattern = new List<int>();
int engine = 1;
foreach (char c in s) {
if (!map.ContainsKey(c)) {
map[c] = engine++;
}
pattern.Add(map[c]);
}
return pattern;
}
public bool IsIsomorphic(string s, string t) {
return GeneratePattern(s).SequenceEqual(GeneratePattern(t));
}
}
Implement a pattern generation routine that relies on a fixed version of dictionary marking, accordingly generating patterns for comparison.