205. Isomorphic Strings

[mah-shamim]

Topics: Hash Table, String

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.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

[mah-shamim]

We can use two hash maps (or associative arrays in PHP) to track the mappings of characters from s to t and vice versa.

Let's implement this solution in PHP: 205. Isomorphic Strings

<?php
function isIsomorphic($s, $t) {
    if (strlen($s) != strlen($t)) {
        return false;
    }

    $mapST = [];
    $mapTS = [];

    for ($i = 0; $i < strlen($s); $i++) {
        $charS = $s[$i];
        $charT = $t[$i];

        // Check if there is a mapping for charS to charT
        if (isset($mapST[$charS])) {
            if ($mapST[$charS] != $charT) {
                return false;
            }
        } else {
            $mapST[$charS] = $charT;
        }

        // Check if there is a mapping for charT to charS
        if (isset($mapTS[$charT])) {
            if ($mapTS[$charT] != $charS) {
                return false;
            }
        } else {
            $mapTS[$charT] = $charS;
        }
    }

    return true;
}

// Test cases
echo isIsomorphic("egg", "add") ? 'true' : 'false'; // Output: true
echo "\n";
echo isIsomorphic("foo", "bar") ? 'true' : 'false'; // Output: false
echo "\n";
echo isIsomorphic("paper", "title") ? 'true' : 'false'; // Output: true
?>

Explanation:

1. Length Check: First, we check if the lengths of the two strings are equal. If not, they cannot be isomorphic.

2. Mapping Creation: We use two associative arrays, $mapST and $mapTS, to track the mappings:

   • $mapST stores the mapping from characters in s to characters in t.
   • $mapTS stores the mapping from characters in t to characters in s.

3. Iteration:

   • We iterate through each character in the strings s and t.
   • If a mapping already exists, we check if it is consistent. If not, we return false.
   • If no mapping exists, we create a new one.

4. Return: If we successfully iterate through the entire string without finding any inconsistencies, we return true, indicating that the strings are isomorphic.

This approach runs in O(n) time complexity, where n is the length of the strings, making it efficient for the input constraints.

[mah-shamim]

Thanks