algoadvance

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.

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.

Clarifying Questions

1. Character Set: Are the strings limited to any specific character set (e.g., only lowercase English letters)?
   • Typically, s and t consist of lowercase English letters, but we can assume they can be any printable ASCII characters unless specified otherwise.
2. String Length: Is there any constraint on the length of the strings s and t?
   • The lengths are typically within a reasonable range to be handled by common algorithms (up to tens of thousands).
3. Empty Strings: Can s and t be empty? How should such cases be handled?
   • Yes, empty strings are valid inputs, and two empty strings are isomorphic by definition.

Code

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    mapping_s_to_t = {}
    mapping_t_to_s = {}

    for char_s, char_t in zip(s, t):
        if char_s in mapping_s_to_t:
            if mapping_s_to_t[char_s] != char_t:
                return False
        else:
            mapping_s_to_t[char_s] = char_t

        if char_t in mapping_t_to_s:
            if mapping_t_to_s[char_t] != char_s:
                return False
        else:
            mapping_t_to_s[char_t] = char_s

    return True

Strategy

1. Initial Check: Begin by checking if the lengths of the two strings are different. If they are, return False immediately since they can’t be isomorphic.

2. Mapping Characters: Use two dictionaries to keep track of the character mappings:
   • mapping_s_to_t: Maps a character from s to t.
   • mapping_t_to_s: Maps a character from t to s.
3. Character-by-Character Comparison:
   • Iterate over the pairs of characters from s and t simultaneously.
   • For each pair (char_s, char_t), check if there is a mapping already established in either direction.
   • If char_s is already mapped to another character, check if it maps to the current char_t. If not, return False.
   • If char_t is already mapped to another character, check if it maps to the current char_s. If not, return False.
   • If there are no conflicts, establish the mapping in both dictionaries.
4. Return: If all checks are passed, return True as the strings are isomorphic.

Time Complexity

• Time Complexity: (O(n)), where (n) is the length of the strings. This is because we iterate through the strings once and perform constant-time operations (dictionary lookups and inserts) for each character.
• Space Complexity: (O(n)) in the worst case, for the space used by the two dictionaries.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?