Given two strings str1 and str2, the task is to check if the two strings are isomorphic to each other.
Two strings str1 and str2 are called isomorphic if there is a one-to-one mapping possible for every character of str1 to every character of str2 and all occurrences of every character in ‘str1’ map to the same character in ‘str2’.
Examples:
Input: str1 = “aab”, str2 = “xxy”
Output: True
Explanation: ‘a’ is mapped to ‘x’ and ‘b’ is mapped to ‘y’.Input: str1 = “aab”, str2 = “xyz”
Output: False
Explanation: One occurrence of ‘a’ in str1 has ‘x’ in str2 and other occurrence of ‘a’ has ‘y’.
Approach: The approach based on frequency counting and dictionary are mentioned in the previous post. Here we will be discussing the solution using STL. The idea to this is mentioned below:
Use the unordered map data structure for hashing purpose by using the character of str1 as the key and the difference between the ASCII value of the two characters on the same index as the value.
If the same character repeats itself then check whether the previously hashed value matches it or not which confirms if a character is mapped to only one character.
Follow the below steps to solve the problem:
- Check whether the size of str1 is the same as str2 or not,
- If not then return false.
- Now declare an unordered map and start to iterate from index 0 of str1.
- For each character check whether the current character already occurred or not
- If not, then add the key-value pair as mentioned above.
- Otherwise, check if map[str1[curr_index]] = str1[curr_index] – str2[curr_index]. If not equal then return false.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// This function returns true if// str1 and str2 are isomorphicbool areIsomorphic(string str1, string str2){ // Unordered map to store the // Hash value for each string unordered_map<char, int> fre; int size1 = str1.size(); int size2 = str2.size(); // Check whether size equals or not, // if not then isomorphism // can't be achieved if (size1 != size2) return false; for (int i = 0; i < size1; i++) { // Check whether current character // already hashed or not if (fre.find(str1[i]) == fre.end()) { // If not then assign // hash value to it fre[str1[i]] = str1[i] - str2[i]; } // If already hashed then compare // with its current hashed value else if (fre[str1[i]] != (str1[i] - str2[i])) { return false; } } return true;}// Driver programint main(){ string s1 = "aab"; string s2 = "xxy"; // Calling function bool ans = areIsomorphic(s1, s2); if (ans) cout << "True"; else cout << "False"; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // This function returns true if // str1 and str2 are isomorphic public static boolean areIsomorphic(String str1, String str2) { // Unordered map to store the // Hash value for each string HashMap<Character, Integer> fre = new HashMap<>(); int size1 = str1.length(); int size2 = str2.length(); // Check whether size equals or not, // if not then isomorphism // can't be achieved if (size1 != size2) return false; for (int i = 0; i < size1; i++) { // Check whether current character // already hashed or not if (fre.get(str1.charAt(i)) == null) { // If not then assign // hash value to it fre.put( str1.charAt(i), (int)(str1.charAt(i) - str2.charAt(i))); } // If already hashed then compare // with its current hashed value else if (fre.get(str1.charAt(i)) != (int)((str1.charAt(i) - str2.charAt(i)))) { return false; } } return true; } public static void main(String[] args) { String s1 = "aab"; String s2 = "xxy"; // Calling function boolean ans = areIsomorphic(s1, s2); if (ans != false) System.out.print("True"); else System.out.print("False"); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code for the above approach# This function returns true if# str1 and str2 are isomorphicdef areIsomorphic(str1, str2): # Unordered map to store the # Hash value for each string fre = dict() size1 = len(str1) size2 = len(str2) # Check whether size equals or not # if not then isomorphism # can't be achieved if size1 != size2: return False for i in range(size1): # Check whether current character # already hashed or not if str1[i] not in fre: # If not then assign # hash value to it fre[str1[i]] = ord(str1[i]) - ord(str2[i]) # If already hashed then compare # with its current hashed value else: if fre[str1[i]] != (ord(str1[i]) - ord(str2[i])): return False return True# Driver codes1 = "aab"s2 = "xxy"# function callprint(areIsomorphic(s1, s2))# this code is contributed by phasing17 |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // This function returns true if // str1 and str2 are isomorphic static bool areIsomorphic(String str1, String str2) { // Unordered map to store the // Hash value for each string Dictionary<char, int> fre = new Dictionary<char, int>(); int size1 = str1.Length; int size2 = str2.Length; // Check whether size equals or not, // if not then isomorphism // can't be achieved if (size1 != size2){ return false; } for (int i = 0 ; i < size1 ; i++) { // Check whether current character // already hashed or not if (!fre.ContainsKey(str1[i])) { // If not then assign // hash value to it fre.Add(str1[i], ((int)str1[i] - (int)str2[i])); } // If already hashed then compare // with its current hashed value else if (fre[str1[i]] != ((int)str1[i] - (int)str2[i])){ return false; } } return true; } // Driver Code public static void Main(string[] args){ String s1 = "aab"; String s2 = "xxy"; // Calling function bool ans = areIsomorphic(s1, s2); if (ans){ Console.WriteLine("True"); }else{ Console.WriteLine("False"); } }}// This code is contributed by entertain2022. |
Javascript
<script>// JS code to implement the approach// This function returns true if// str1 and str2 are isomorphicfunction areIsomorphic(str1, str2){ // Unordered map to store the // Hash value for each string var fre = {}; var size1 = str1.length; var size2 = str2.length; // Check whether size equals or not, // if not then isomorphism // can't be achieved if (size1 != size2) return false; for (var i = 0; i < size1; i++) { // Check whether current character // already hashed or not if (fre.hasOwnProperty(str1[i])) { // If not then assign // hash value to it fre[str1[i]] = str1[i] - str2[i]; } // If already hashed then compare // with its current hashed value else if (fre[str1[i]] != (str1[i] - str2[i])) { return false; } } return true;}// Driver programvar s1 = "aab";var s2 = "xxy";// Calling functionvar ans = areIsomorphic(s1, s2);if (ans) document.write("True");else document.write("False");// This code was contributed by phasing17</script> |
Output
True
Time Complexity: O(N) where N is the size of the strings
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
