Isomorphic Strings

LeetCode Q 205 - Isomorphic Strings

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

Two strings 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.

Similar Questions: Sentence Similarity

Solution

Solution 1: HashMap

key is the char, value is the corresponding char.
One tricky is: if (map.containsValue(chs)) return false;
that is if we map ‘a’ to ‘b’, we cannot map ‘c’ to ‘b’ again.
The mapping should be one-to-one.

Code:

public boolean isIsomorphic(String s, String t) {
	if (s.length() != t.length()) return false;
	Map<Character, Character> map = new HashMap<>();
	for (int i = 0; i < s.length(); i++) {
		char chs = s.charAt(i)), cht = t.charAt(i);
		if (map.containsKey(s.charAt(i))) {
			if (!map.get(chs) == cht) return false;
		} else {
			if (map.containsValue(chs)) return false;
			map.put(chs, cht);
		}
	}	
	return true;
}

Solution 2: Use two arrays

Instead of using a map, we can use two arrays. First, we traverse strings s and t. At index i, we checkif (S[chs - 'a']) != T[cht - 'a']. There are 3 cases.

1. we never encountered chs and cht before, then their values should both be 0, then we cannot go in the if condition;
2. we encountered chs and cht before, then if their values is the same, then the chars mapping remains same as before, then we then we cannot go in the if condition;
3. if their values is not same, meaning previously we don’t mapping chs to cht, that is the current mapping is different with previous mapping, then return false;

Code:

public boolean isIsomorphic(String s, String t) { 
	if (s.length() != t.length()) return false;
	int[] S = new int[26], T = new int[26];
	for (int i = 0; i < s.length(); i++) {
		char chs = s.charAt(i), cht = t.charAt(j);
		if (S[chs - 'a'] != T[cht - 'a']) return false;
		S[chs - 'a'] = i + 1; T[cht - 'a'] = i + 1; 
	}
	return true;
}