C++ Check if two given strings are isomorphic to each other














































C++ Check if two given strings are isomorphic to each other



Check if two given strings are isomorphic to each other

Given two strings 'str1' and 'str2', check if these 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 while preserving the order. All occurrences of every character in %u2018str1%u2019 should map to the same character in %u2018str2%u2019


Examples

Input:  str1 = "egg", str2 = "add"

Output: True

'e' is mapped to 'a' and 'g' is mapped to 'd'.


Input:  str1 = "aabbcc", str2 = "xxyyzx"

Output: False

One occurrence of 'c' in str1 has 'z' in str2 and other occurrence of 'c' has 'x'. It is not one to one mapping.


Algorithm

1) If lengths of string1 and string2 are not same, return false.

2) Do following for every character in string1 and string2

   a) If this character is seen first time in string1,

      then current of string 2 must have not appeared before.

      (i) If current character of string2 is seen, return false.

          Mark current character of string2 as visited.

      (ii) Store mapping of current characters.

   b) Else check if previous occurrence of string1 mapped

      to same character.


Implementation

#include <bits/stdc++.h>
using namespace std;
 
bool checkIsomorphic(string s1string s2
  
    int l1 = s1.length(), l2 = s2.length(); 
  
    // Length of both strings must be same for one to one 
    if (l1 != l2
      return false
  
    // To mark visited characters in s2 
    bool visited[256] = {false}; 
  
    // To store mapping of every character from s1 to 
    // that of s2. Initialize all entries of map as -1. 
    int map[256]; 
    memset(map, -1sizeof(map)); 
    
    for (int i = 0i < l2i++) 
    { 
        // If current character of s1 is not seen yet 
        if (map[s1[i]] == -1
        { 
            // If current character of s2 is already 
            // seen, one to one mapping not possible 
            if (visited[s2[i]] == true
                return false
  
            // Mark current character of s2 as visited 
            visited[s2[i]] = true
  
            // Store mapping of current characters 
            map[s1[i]] = s2[i]
        } 
  
        // If this is not first appearance of current 
        // character in s1, then check if previous 
        // appearance mapped to same character of s2 
        else if (map[s1[i]] != s2[i]
            return false
    } 
  
    return true

int main() {
 
    string str1 = "paper"str2 = "title";
    
    if(checkIsomorphic(str1str2))
        cout << "True";
    else 
        cout << "False";
 
    return 0;
}


Output

True





Comments