205. Isomorphic Strings

Description

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

Explanation:

The strings s and t can be made identical by:

• Mapping 'e' to 'a'.
• Mapping 'g' to 'd'.

Example 2:

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

Output: false

Explanation:

The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.

Example 3:

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

Output: true

Constraints:

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

Solution

To determine whether two strings are isomorphic, we can transform both strings into a common pattern by tracking the first occurrence of each character.

For example, the strings paper and title share the same pattern: abacd. That is, each character is replaced with the order in which it first appeared. If a character has appeared before, we reuse the same marker.

We can use a HashMap to store the first occurrence index of each character. For instance, in paper, 'p' appears first and gets index 1, 'a' gets 2, 'p' reuses 1, and so on. This results in a pattern like 12134.

While constructing the patterns for both strings simultaneously, we can compare the index values at each position. If they differ at any point, the strings are not isomorphic.

Code

import java.util.HashMap;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Integer> sh = new HashMap<Character, Integer>();
        HashMap<Character, Integer> th = new HashMap<Character, Integer>();
        int ns = 1, nt = 1;
        int cur_s = 0, cur_t = 0;
        char char_s, char_t;

        for (int i = 0; i < s.length(); ++i) {
            char_s = s.charAt(i);
            char_t = t.charAt(i);
            if (sh.containsKey(char_s)) {
                cur_s = sh.get(char_s);
            } else {
                cur_s = ns;
                sh.put(char_s, ns);
                ++ns;
            }
            if (th.containsKey(char_t)) {
                cur_t = th.get(char_t);
            } else {
                cur_t = nt;
                th.put(char_t, nt);
                ++nt;
            }

            if (cur_s != cur_t) {
                return false;
            }
        }

        return true;
    }
}

Time Complexity: O(n)
We traverse the strings once, where n is the length of the input.

Space Complexity: O(n)
In the worst case, each character is unique, so we may need to store up to n mappings.

Optimized Code

import java.util.HashMap;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] mapS = new int[256];
        int[] mapT = new int[256];
        int index = 1;

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

            if (mapS[c1] == 0 && mapT[c2] == 0) {
                mapS[c1] = index;
                mapT[c2] = index;
                index++;
            } else if (mapS[c1] != mapT[c2]) {
                return false;
            }
        }
        return true;
    }
}

The optimized solution uses int[] arrays instead of HashMap. Since the input only contains ASCII characters, we can safely use character ASCII values as indices.
This avoids the overhead of auto-boxing (converting primitives to wrapper objects), which improves both speed and memory usage.