Technical Interview Question: Isomorphic Strings

You are given two strings s and t. Determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t.

Implement a function isIsomorphic to return true if the given strings are isomorphic, otherwise return false.

Function Signature

public boolean isIsomorphic(String s, String t)

Example

Input:
s = "egg", t = "add"
Output:
true

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

Constraints

• The length of s and t is the same.
• All characters of s and t are lowercase English letters.

Answer:

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    Map<Character, Character> map = new HashMap<>();
    Set<Character> usedChars = new HashSet<>();

    for (int i = 0; i < s.length(); i++) {
        char sChar = s.charAt(i);
        char tChar = t.charAt(i);

        // Check if character has been mapped before
        if (map.containsKey(sChar)) {
            if (map.get(sChar) != tChar) {
                return false; // If the mapping does not match, return false
            }
        } else {
            if (usedChars.contains(tChar)) {
                return false; // If the character at 't' has been mapped before with another character from 's', return false
            } else {
                map.put(sChar, tChar); // Map new characters
                usedChars.add(tChar); // Add the character at 't' to usedChars set
            }
        }
    }

    return true; // Both input strings are isomorphic
}

Explanation

1. We start by checking if the lengths of both input strings are the same. If not, we return false, as isomorphic strings must have the same length.

2. We then declare a HashMap map to store the mapping of characters from s to t, along with a HashSet usedChars to store the characters already mapped to t.

3. We iterate through each character of s and t using a for loop, comparing the characters at the same index in both strings.

4. During iteration, we check if the character from s has been mapped before. If so, we verify whether the corresponding character from t matches the previous mapping. If it does not match, we return false, as isomorphic strings should have consistent character mappings.

5. If the character has not been mapped before, we check if the character at index t has already been mapped to another character in s. If it has, we return false as it violates the isomorphic condition.

6. If the character at index t has not been mapped before, we add the character mapping to the map and mark the t character as used in the usedChars set.

7. After iterating through both strings, if no inconsistencies were found, we return true, indicating that the given strings are isomorphic.