Skip to content

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

Comments