Description

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:

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

Using HashMap

One way to solve this could be using HashMap. If we keep first string s characters as key and second string t characters as values. We have to make sure that each time the same character maps to same value and we have to make sure the mapping from s to t and also the other way around from t to s characters.

 1class Solution {
 2    public boolean isIsomorphic(String s, String t) {
 3        Map<Character, Character> mapSToT = new HashMap<>();
 4        Map<Character, Character> mapTToS = new HashMap<>();
 5        for (int i = 0; i < s.length(); i++ ) {
 6            char sChar = s.charAt(i);
 7            char tChar = t.charAt(i);
 8            if (!mapSToT.containsKey(sChar) && !mapTToS.containsKey(tChar)) {
 9                mapSToT.put(sChar, tChar);
10                mapTToS.put(tChar, sChar);
11            } else if (mapSToT.containsKey(sChar) && mapTToS.containsKey(tChar)) {
12                if (mapSToT.get(sChar) != tChar || mapTToS.get(tChar) != sChar) {
13                    return false;
14                }
15            } else { // one map contains key but other does not.
16                return false;
17            }
18        }
19        return true;
20    }
21}
  • Time Complexity: O(n)
  • Space Complexity: O(i + j) where i is number of unique characters in string s and j unique characters in t.

Using Array

The problem states that the strings contain valid ascii characters. That means there can be one of 0-256 characters to represent these ascii characters. We could use array to store the mapping from s to t and vice a versa. Now, arrays by default have value of 0 which is actually valid ascii character. So, we have to change the arrays to default value of -1.

 1class Solution {
 2    private static final int ARRAY_SIZE = 256;
 3
 4    public boolean isIsomorphic (String s, String t) {
 5        int[] mapSToT = new int[ARRAY_SIZE];
 6        int[] mapTToS = new int[ARRAY_SIZE];
 7
 8        Arrays.fill(mapSToT, -1);
 9        Arrays.fill(mapTToS, -1);
10
11        for (int i = 0; i < s.length(); i++) {
12            char sChar = s.charAt(i);
13            char tChar = t.charAt(i);
14            if (mapSToT[sChar] == -1 && mapTToS[tChar] == -1) {
15                mapSToT[sChar] = tChar;
16                mapTToS[tChar] = sChar;
17            } else if (mapSToT[sChar] != tChar || mapTToS[tChar] != sChar) {
18                return false;
19            }
20        }
21        return true;
22    }
23}
  • Time Complexity: O(n)
  • Space Complexity: O(1) as it is fixed as 256 characters each in both arrays.