Problem

Given two strings s and t, determine if they are isomorphic.

Definition

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example

Example 1:

1
2
3
4

Input:
s = "egg", t = "add"
Output:
 true

Example 2:

1
2
3
4

Input:
s = "foo", t = "bar"
Output:
 false

Example 3:

1
2
3
4

Input:
s = "paper", t = "title"
Output:
 true

Solution

Note, isomorphic mapping is both ways, i.e. in foo and bar; f maps to b but b also maps to f. Lets look at example.

Suppose, we have s as foot and t as baab. If we use 1 map, we have following map

1
2
3
4
5

a --> b
p --> a
p --> a // p already exists in map, map.get(s[i]) == t[i]
l --> b
e --> c

If we just check $s[i]$ matching $t[i]$ (without matching $t[i]$ back to $s[i]$ ) we will see that both strings are isomorphic, but that is incorrect. The reason is both a and l mapped to b.

Method 1 - Using 1 Hashmap ❌

We can define a map which tracks the char-char mappings. If a value is already mapped, it can not be mapped again.

Time complexity O(n^2) by mistake:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public boolean isIsomorphic(String s, String t) {
	if (s == null && t == null)
		return true;
	else if (s == null || t == null){
		return false;
	}

	if (s.length() != t.length())
		return false;

	Map<Character, Character> map = new HashMap<> ();

	for (int i = 0; i<s.length(); i++) {
		char c1 = s.charAt(i);
		char c2 = t.charAt(i);

		if (map.containsKey(c1)) {
			if (map.get(c1) != c2) // if not consistant with previous ones
				return false;
		} else {
			if (map.containsValue(c2)) //if c2 is already being mapped. Time complexity O(n) here
				return false;
			map.put(c1, c2);
		}
	}

	return true;
}
  • Time complexity:O(n^2)  (as containsValue take O(n) and as it is nested under loop, it is O(n^2))
  • Space complexity:O(n)

Method 2 - Using 2 Hashmaps 🏆

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public boolean isIsomorphic(String s, String t) {
	if (s.length() != t.length()) {
		return false;
	}
	
	Map<Character, Character> first = new HashMap<>();
	Map<Character, Character> second = new HashMap<>();
	
	for (int i = 0; i < s.length(); i++) {
		char c = s.charAt(i);
		char d = t.charAt(i);
		
		if (first.containsKey(c)) {
			char dStored = first.get(c);
			if (d != dStored) {
				return false;
			}
		} else {
			first.put(c, d);
			if (second.containsKey(d)) {
				return false;
			}
			second.put(d, c);
		}
	}
	return true;
	
}
  • Time complexity:O(n) 
  • Space complexity:O(n)