205. Isomorphic Strings

Intuition

Two strings are isomorphic if every character in the first string can be uniquely replaced to get the second string, preserving the order. This means:

• Characters at the same index in both strings must have a one-to-one mapping.

• No two different characters from the first string can map to the same character in the second string, and vice versa.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N)$

Code

public boolean isIsomorphic(String source, String target) {
    // Strings of different lengths cannot be isomorphic
    if (source.length() != target.length()) return false;

    // Arrays to hold character mappings (ASCII size 256)
    char[] mapTargetToSource = new char[256];
    char[] mapSourceToTarget = new char[256];

    for (int i = 0; i < source.length(); ++i) {
        char sourceChar = source.charAt(i);
        char targetChar = target.charAt(i);

        // Check if targetChar is already mapped to a different sourceChar
        if (mapTargetToSource[targetChar] != '\0' && mapTargetToSource[targetChar] != sourceChar) {
            return false;
        }

        // Check if sourceChar is already mapped to a different targetChar
        if (mapSourceToTarget[sourceChar] != '\0' && mapSourceToTarget[sourceChar] != targetChar) {
            return false;
        }

        // Create the character mappings
        mapTargetToSource[targetChar] = sourceChar;
        mapSourceToTarget[sourceChar] = targetChar;
    }

    return true;
}