205. Isomorphic Strings Leetcode Solution
Isomorphic Strings Leetcode Problem :
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 :
Input: s = "egg", t = "add"
Output: true
Isomorphic Strings Leetcode Solution :
Constraints :
- 1 <= s.length <= 5 * 104
- t.length == s.length
- s and t consist of any valid ascii character.
Example 1:
- Input: s = “foo”, t = “bar”
- Output: false
Example 2:
- Input: s = “paper”, t = “title”
- Output: true
Intuition :
Given two strings, s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be mapped to the characters in t in a one-to-one relationship.
Approach :
The provided C++ code uses a simple approach to determine if two strings are isomorphic. Here’s a step-by-step explanation:
- Length Check:
- Check if the lengths of strings s and t are equal. If not, return false because strings of different lengths cannot be isomorphic.
- Initialize Data Structures:
- Create a vector visited of size 128, initialized to zeros. This vector is used to track the mapping of characters in string s to characters in string t.
- Iterate Through Characters:
- Use a for loop to iterate through each character of the strings s and t simultaneously.
- For each character at index i:
- Retrieve the characters charS and charT from strings s and t, respectively.
- Check Unvisited Character in s:
- If visited[charS] is zero, it means the character charS in string s is not mapped to any character in t yet.
- Check if the corresponding character charT in string t has already been used as a mapping for another character in s.
- If yes, return false because two characters in s cannot be mapped to the same character in t.
- If no, establish a mapping by setting visited[charS] to charT.
- Check if the corresponding character charT in string t has already been used as a mapping for another character in s.
- If visited[charS] is zero, it means the character charS in string s is not mapped to any character in t yet.
- Check Previously Visited Character in s:
- If visited[charS] is not zero, it means the character charS in string s has been mapped before.
- Check if the current mapping is consistent with the character charT in string t.
- If not consistent, return false because the strings are not isomorphic.
- Check if the current mapping is consistent with the character charT in string t.
- If visited[charS] is not zero, it means the character charS in string s has been mapped before.
- Return Result:
- After iterating through all characters, if no inconsistencies are found, return true indicating that the strings are isomorphic.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
bool isIsomorphic(std::string s, std::string t) {
if (s.length() != t.length()) {
return false; // Different lengths cannot be isomorphic
}
std::vector< char> visited(128, 0); // Track characters visited in s
for (int i = 0; i < s.length(); i++) {
char charS = s[i];
char charT = t[i];
if (visited[charS] == 0) {
// Check if the character in t has already been mapped
if (std::count(visited.begin(), visited.end(), charT) > 0) {
return false;
}
visited[charS] = charT; // Map the character in s to the character in t
} else if (visited[charS] != charT) {
return false;
}
}
return true;
}
};
Java
class Solution {
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) {
return false; // Different lengths, not isomorphic
}
HashMap< Character, Character> sToTMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char charS = s.charAt(i);
char charT = t.charAt(i);
if (sToTMap.containsKey(charS)) {
if (sToTMap.get(charS) != charT) {
return false; // Inconsistent mapping
}
} else {
if (sToTMap.containsValue(charT)) {
return false; // Collision, not isomorphic
}
sToTMap.put(charS, charT);
}
}
return true;
}
}
Python
class Solution(object):
def isIsomorphic(self, s, t):
map1 = []
map2 = []
for idx in s:
map1.append(s.index(idx))
for idx in t:
map2.append(t.index(idx))
if map1 == map2:
return True
return False
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment