grid47 Exploring patterns and algorithms
Oct 17, 2024
5 min read
Solution to LeetCode 205: Isomorphic Strings Problem
Two strings s and t are isomorphic if you can replace the characters in s to get t. The replacement should be such that each character in s maps to exactly one character in t, and the mapping must preserve the order of characters. No two characters in s or t can map to the same character.
Problem
Approach
Steps
Complexity
Input: The input consists of two strings s and t.
Example: s = 'abc', t = 'xyz'
Constraints:
• 1 <= s.length, t.length <= 5 * 10^4
• s.length == t.length
• Both s and t consist of printable ASCII characters.
Output: Return true if the two strings s and t are isomorphic, otherwise return false.
Example: Output: true
Constraints:
• The output should be a boolean value indicating whether the strings are isomorphic.
Goal: The goal is to check if the characters of s can be uniquely mapped to the characters of t without violating the mapping rules.
Steps:
• Iterate through each character in both strings.
• Use two maps: one to track the mapping from s to t and another from t to s.
• For each character in s and t, check if a consistent mapping exists.
Goal: Ensure that the solution works efficiently for large inputs.
Steps:
• Both strings must have the same length.
• The strings consist of printable ASCII characters.
Assumptions:
• The input strings are valid and consist of printable ASCII characters.
• Input: s = 'abc', t = 'xyz'
• Explanation: In this case, 'a' maps to 'x', 'b' maps to 'y', and 'c' maps to 'z'. Since no characters map to the same character, the strings are isomorphic.
• Input: s = 'foo', t = 'bar'
• Explanation: Here, 'o' maps to both 'a' and 'r', so the strings are not isomorphic.
Approach: The problem can be solved by checking if there is a consistent one-to-one mapping between characters of s and t.
Observations:
• This problem requires mapping characters between two strings while ensuring uniqueness in both directions.
• Using two hash maps to track mappings from s to t and t to s can help efficiently solve this problem.
Steps:
• Initialize two maps: one for s -> t mapping and one for t -> s mapping.
• Iterate through both strings simultaneously.
• For each character in s and t, check if the character is already mapped to a different one in either direction.
• If a consistent mapping is found for all characters, return true. Otherwise, return false.
Empty Inputs:
• Since the strings are guaranteed to have the same length and be non-empty, there will be no empty inputs.
Large Inputs:
• The algorithm must handle large inputs efficiently, given the constraint of up to 50,000 characters.
Special Values:
• When s and t are identical strings, they are always isomorphic.
Constraints:
• The solution must work within the time limits for large inputs.
boolisIsomorphic(string s, string t) {
map<char, char> fwd, rwd;
int n = s.size();
for(int i =0; i < n; i++) {
if (fwd.count(s[i])){
if(fwd[s[i]] != t[i])
returnfalse;
}
if(rwd.count(t[i])){
if(rwd[t[i]] != s[i])
returnfalse;
}
fwd[s[i]] = t[i];
rwd[t[i]] = s[i];
}
returntrue;
}
1 : Function Definition
boolisIsomorphic(string s, string t) {
Define the function `isIsomorphic` that checks if two strings `s` and `t` are isomorphic. Two strings are isomorphic if characters in `s` can be mapped to characters in `t` in a consistent one-to-one manner.
2 : Variable Initialization
map<char, char> fwd, rwd;
Initialize two maps, `fwd` and `rwd`, to store the character mappings from `s` to `t` and from `t` to `s`, respectively.
3 : String Length Calculation
int n = s.size();
Calculate the length of string `s` and store it in the variable `n`. The same length applies to string `t`.
4 : For Loop
for(int i =0; i < n; i++) {
Start a for loop to iterate through each character of the strings `s` and `t`.
5 : Check Forward Mapping
if (fwd.count(s[i])){
Check if the character `s[i]` has already been mapped in the `fwd` map.
6 : Validate Forward Mapping
if(fwd[s[i]] != t[i])
If `s[i]` is already mapped, check if the current mapping matches `t[i]`. If not, the strings are not isomorphic.
7 : Return False
returnfalse;
Return `false` if the mappings are inconsistent.
8 : Check Reverse Mapping
if(rwd.count(t[i])){
Check if the character `t[i]` has already been mapped in the `rwd` map.
9 : Validate Reverse Mapping
if(rwd[t[i]] != s[i])
If `t[i]` is already mapped, check if the current mapping matches `s[i]`. If not, the strings are not isomorphic.
10 : Return False
returnfalse;
Return `false` if the mappings are inconsistent.
11 : Forward Mapping Assignment
fwd[s[i]] = t[i];
Assign the mapping `s[i]` to `t[i]` in the `fwd` map.
12 : Reverse Mapping Assignment
rwd[t[i]] = s[i];
Assign the mapping `t[i]` to `s[i]` in the `rwd` map.
13 : Return True
returntrue;
Return `true` if no inconsistencies were found, indicating that the strings are isomorphic.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the strings, as we perform a single pass through the strings and constant time operations with hash maps.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for the two hash maps.
