2 strings are said to be isomorphic, if one letter in the first string can be replaced by another letter in the second string.
Example 1: string_1 = add string_2 = egg Output: True Here “a” can be replaced by “e” and “d” can be replaced by “g”. Example 2: string_1 = foo string_2 = bar Output: False Here “f” can be replaced by “b” and “o” can be replaced by, “a”, and “o” again cannot be replaced by “r”. Hence it will return false.
This problem can be solved with the help of 2 hash maps.
We shall mark all the index in both the hash map where the elements are present.
Then check if both the hash map at that index are same. If they are same we shall check at the next index. If they are not same, it means, we have mapped that letter to another. Hence exiting the loop.
In below output will give a clear idea about implementation.
Solution in C++
#include<iostream> #include<string> #include<vector> using namespace std; bool check_isomorphic(string str_1, string str_2) { int hash_map_1[256]={0}; int hash_map_2[256]={0}; for(int i=0;i<str_1.length();i++) { cout<<"Step 1 i = "<<i <<" hash_map_1[str_1[i]] = "<< hash_map_1[str_1[i]]<<" hash_map_2[str_2[i]] = "<< hash_map_2[str_2[i]]<<endl; if(hash_map_1[str_1[i]]!=hash_map_2[str_2[i]]) { return false; } hash_map_1[str_1[i]] = 1; hash_map_2[str_2[i]] = 1; } return true; } int main() { string str_1 = "add"; string str_2 = "egg"; cout<<"===========Test case 1==========="<<endl; cout<<"string 1 = "<<str_1 <<" string 2 = "<<str_2<<endl; if(check_isomorphic(str_1, str_2)) cout<<"\nResult: The 2 strings are isomorphic"<<endl; else cout<<"\nResult: The 2 strings are NOT isomorphic"<<endl; str_1 = "foo"; str_2 = "bar"; cout<<"\n===========Test case 2==========="<<endl; cout<<"string 1 = "<<str_1 <<" string 2 = "<<str_2<<endl; if(check_isomorphic(str_1, str_2)) cout<<"\nResult: The 2 strings are isomorphic"<<endl; else cout<<"\nResult: The 2 strings are NOT isomorphic"<<endl; return true; }
Output:
===========Test case 1=========== string 1 = add string 2 = egg Step 1 i = 0 hash_map_1[str_1[i]] = 0 hash_map_2[str_2[i]] = 0 Step 1 i = 1 hash_map_1[str_1[i]] = 0 hash_map_2[str_2[i]] = 0 Step 1 i = 2 hash_map_1[str_1[i]] = 1 hash_map_2[str_2[i]] = 1 Result: The 2 strings are isomorphic ===========Test case 2=========== string 1 = foo string 2 = bar Step 1 i = 0 hash_map_1[str_1[i]] = 0 hash_map_2[str_2[i]] = 0 Step 1 i = 1 hash_map_1[str_1[i]] = 0 hash_map_2[str_2[i]] = 0 Step 1 i = 2 hash_map_1[str_1[i]] = 1 hash_map_2[str_2[i]] = 0 Result: The 2 strings are NOT isomorphic