205. Isomorphic Strings

Difficulty: Easy

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?

Solution:

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
// 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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub