3. Isomorphic Strings 205

205. Isomorphic Strings

Easy

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

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 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

 

Constraints:

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s and t consist of any valid ascii character.

Accepted

528,011

Submissions

1,249,991

Solution :

6 line code and a good understanding on how the algo works. That's all. It's a very good question indeed and in first thought we go for map. But we even don't need map here. Just a simple array will do the trick.

Approach - Using Map:

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || t == null)
            return false;
        if (s.length() != t.length())
            return false;
        if (s.length() == 0 && t.length() == 0)
            return true;
        HashMap<Character, Character> map = new HashMap<Character, Character>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            Character c = getKey(map, c2);
            if (c != null && c != c1) {
                return false;
            } else if (map.containsKey(c1)) {
                if (c2 != map.get(c1))
                    return false;
            } else {
                map.put(c1, c2);
            }
        }
        return true;
    }

    public Character getKey(HashMap<Character, Character> map, Character target) {
        for (Map.Entry<Character, Character> entry : map.entrySet()) {
            if (entry.getValue().equals(target)) {
                return entry.getKey();
            }
        }
        return null;
    }

}

Approach - Simple Array:

class Solution {
    public boolean isIsomorphic (String s, String t) {
        int[] m = new int[512];
        for (int i = s.length()-1; i > -1; i--) {
            if (m[s.charAt(i)] != m[t.charAt(i)+256]) 
                return false;
            m[s.charAt(i)] = m[t.charAt(i)+256] = i;
        }
        return true;
    }
}

Follow up : I was given this question in an interview ytd. I got a followup which asks me to group the isomorphic strings as well

e.g.

input:
['aab', 'xxy', 'xyz', 'abc', 'def', 'xyx']

return:
[
['xyx'], 
['xyz', 'abc', 'def'], 
['aab', 'xxy']
]

I did a brute force approach, O(N^3), reusing theisIsomorphic() but it is not that good. Any better ideas?