CODEWITHSUNDEEP
c++
user11281642
user11281642

Reputation:

How do I find if two strings is isomorphic of not?

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool is_isomorphic(string input1, string input2)
{
    if(input1.length()!= input2.length())
        return  false;

    vector<int> diff_arr(26, -40);//Initialise with some random value.

    for(int  i = 0 ; i < input1.length(); i++){
        if(diff_arr[input1[i]-'a'] == -40)
            diff_arr[input1[i]-'a'] = input1[i] - input2[i];
        else{
            if(diff_arr[input1[i]-'a'] != input1[i] - input2[i])
                return false;
        }
    }

    return true;
}

int main() {
    cout<<is_isomorphic("abcd", "aabb");
    return 0;
}

My logic is that if characaters could be replaced with exact same characters in the second string then the character-wise difference has to be the same throughout.

The logic is failing in the above case.

Upvotes: 0

Views: 226

Answers (2)

J&#233;r&#244;me Mign&#233;
J&#233;r&#244;me Mign&#233;

Reputation: 244

You need 2 arrays, one to know which character of input2 correspond to a given character of input1, and a second to check if a character of input2 is not already affected to a character of input1.

#include <iostream>
#include <string>

using namespace std;

bool is_isomorphic(const string& input1, const string& input2)
{
    if (input1.length() != input2.length()) {
        return false;
    }

    char map[256]{};
    bool used[256]{};

    for (size_t i = 0; i < input1.length(); i++) {
        unsigned char val1 = input1[i];
        if (!map[val1]) {
            unsigned char val2 = input2[i];
            if (used[val2]) {
                return false;
            }
            map[val1] = input2[i];
            used[val2] = true;
        } else
        if (map[val1] != input2[i]) {
            return false;
        }
    }

    return true;
}

int main() {
    cout << is_isomorphic("abcd", "aabb") << endl;
    cout << is_isomorphic("abcdb", "zerte") << endl;
    return 0;
}

Upvotes: 1

Oliort UA
Oliort UA

Reputation: 1647

You also need to check if two characters from input1 do not map to same character in input2.

#include <iostream>
#include <string>
#include <map>
#include <set>

using namespace std;

bool is_isomorphic(string input1, string input2)
{
    if(input1.length()!= input2.length())
        return  false;

    set<char> usedLetters;
    map<char, char> transformations;

    for(int i = 0 ; i < input1.length(); i++) {
        auto iter = transformations.find(input1[i]);
        if (iter != transformations.end()) {
            if (iter->second == input2[i]) continue;
            else return false;
        }
        if (usedLetters.count(input2[i])) return false;
        usedLetters.insert(input2[i]);
        transformations[input1[i]] = input2[i];
    }

    return true;
}

int main() {
    cout<<is_isomorphic("abcd", "aabb");
    return 0;
}

Upvotes: 1

Related Questions