205. Isomorphic Strings
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 40.6%
Problem Breakdown
The problem asks us to determine if two strings s and t are isomorphic. Two strings are considered isomorphic if the characters in s can be replaced to get t, with the following conditions:
- All occurrences of a character in
smust be replaced with another character while preserving the order. - No two characters may map to the same character, but a character may map to itself.
Inputs:
- Two strings
sandt.
Outputs:
- A boolean value indicating whether the strings are isomorphic or not.
Implicit Constraints/Edge Cases:
- The lengths of
sandtare equal. - Strings consist of valid ASCII characters.
- Consider edge cases like empty strings, single-character strings, and strings with all identical characters.
Intuition
A brute-force approach would involve checking every possible mapping from characters in s to characters in t, which is computationally expensive. Instead, we can use a more efficient approach by leveraging hash tables (dictionaries) to track the character mappings between s and t.
The key insight is that for two strings to be isomorphic:
- Each character in
smust map uniquely to a character int. - The mapping should be consistent across all occurrences of each character.
Approach
We will use two hash tables (dictionaries) to keep track of the mappings from characters in s to characters in t, and vice versa. As we iterate through the strings, we check if the current characters have a consistent mapping:
- If a character from
sis already mapped to a different character int, returnFalse. - If a character from
tis already mapped to a different character ins, returnFalse. - If no such inconsistencies are found, the strings are isomorphic.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the strings. We iterate through each string once.
- Space Complexity: O(1) since the hash tables will store at most 256 entries (one for each possible ASCII character).
Solution
def isIsomorphic(s: str, t: str) -> bool:
if len(s) != len(t):
return False
# Dictionaries to store mappings from s to t and t to s
map_s_to_t = {}
map_t_to_s = {}
for char_s, char_t in zip(s, t):
# Check mapping from s to t
if char_s in map_s_to_t:
if map_s_to_t[char_s] != char_t:
return False
else:
map_s_to_t[char_s] = char_t
# Check mapping from t to s
if char_t in map_t_to_s:
if map_t_to_s[char_t] != char_s:
return False
else:
map_t_to_s[char_t] = char_s
return True
Edge Cases Handled
- Empty Strings: The function will correctly return
Truefor two empty strings. - Single Character Strings: The function will handle single-character strings and return
Trueif they are identical, otherwiseFalse. - Strings with All Identical Characters: The function will correctly map identical characters to each other.
- Different Lengths (though per problem constraints, this won’t occur): The function checks for length equality at the start and returns
Falseimmediately if lengths differ.