c++ - 如何查找两个字符串是否同构？

#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;
}

我的逻辑是，如果可以在第二个字符串中用完全相同的字符替换字符，则整个字符之间的差异必须相同。

在上述情况下，逻辑失败。

最佳答案

您还需要检查input1中的两个字符是否未映射到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;
}

关于c++ - 如何查找两个字符串是否同构？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55431943/