Isomorphic Strings

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.

Examples

Example 1:

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

Example 2:

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

Example 3:

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

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:

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 🏆

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)