当您将一个包含字符串索引的映射索引设置为另一个字符串索引值时会发生什么？

Question

bool isIsomorphic(std::string s, std::string t) {
    //create hashmap
    std::map<char, char> ms;
    std::map<char, char> mt;
    
    for (int i = 0; i < s.size(); i++)
    {
        ms[s[i]] = t[i];
        mt[t[i]] = s[i];
    }
    
    for (int i = 0; i < s.size(); i++)
    {
        if (ms[s[i]] != t[i] || mt[t[i]] != s[i])
            return false;
    }
    return true;
}

我正在查看这个寻找同构字符串问题的解决方案，但我无法理解

部分发生的事情

ms[s[i]] = t[i];
mt[t[i]] = s[i];

字符串从来没有放在map里面，但是我们在设置map，用字符串的索引到另一个字符串的索引？我无法解决这个问题。我只是通过设置 ms[i] = t[i] 并以这种方式进行比较来尝试这个问题，但它不起作用。我意识到我只是不知道发生了什么。

如果有人能解释一下，我将不胜感激。

Answer 1

让我们首先描述如何检查两个字符串是否同构。根据educative.io:

Two strings are isomorphic if one-to-one mapping is possible for every character of the first string to every character of the second string, and vice-versa.

示例 1：“egg”和“add”是同构的，其中：

Mapping of characters from first string to second string	Mapping of characters from second string to first string
'e' maps to 'a'	'a' maps to 'e'
'g' maps to 'd'	'd' maps to 'g'

示例 2：“badc”和“baba”不是同构的，因为：

Mapping of characters from first string to second string	Mapping of characters from second string to first string
'b' maps to 'b'	'b' maps to 'b'
'a' maps to 'a'	'a' maps to 'a'
'd' maps to 'b'	~~'b' maps to 'd'~~
'c' maps to 'a'	~~'a' maps to 'c'~~

在这里，我们可以看到从第一个字符串到第二个字符串的字符是一对一的映射，但是从第二个字符串到第一个字符串的字符是一对多的映射（例如，'b'映射到'b' 和 'd'，'a' 映射到 'a' 和 'c')。

示例 3：“foo”和“bar”不是同构的，因为：

Mapping of characters from first string to second string	Mapping of characters from second string to first string
'f' maps to 'b'	'b' maps to 'f'
'o' maps to 'a'	'a' maps to 'o'
~~'o' maps to 'r'~~	'r' maps to 'o'

在这里，从第一个字符串到第二个字符串的字符进行一对多映射（例如，'o' 映射到 'a' 和 'r'）。

所以，这里的关键是从第一个字符串到第二个字符串的映射以及从第二个字符串到第一个字符串的映射都需要是一对一的。在第 ms[s[i]] = t[i] 行，此代码将第一个字符串的字符映射到第二个字符串的相应字符；在第 mt[t[i]] = s[i] 行，它在相反方向进行映射。为了同构，在这个方向上的映射需要是一对一的。

我希望这个例子能消除您对双向映射的必要性的疑虑。您甚至可以进一步提高代码的复杂性。您可以通过单次传递（而不是两次）来确定这两个字符串是否同构。这是代码：

bool isIsomorphic(string s, string t) {
    map<char, char> ms;
    map<char, char> mt;

    for(int i=0; i<s.length(); i+=1) {
        if(ms.find(s[i]) == ms.end() && mt.find(t[i]) == mt.end()) {
            ms[s[i]] = t[i];
            mt[t[i]] = s[i];
        }
        else if((ms[s[i]] != t[i]) || (mt[t[i]] != s[i])) return false;
    }

    return true;
}

当您将一个包含字符串索引的映射索引设置为另一个字符串索引值时会发生什么？

What happens when you set a map index, with a string index inside, to another string index value?

c++

arrays

indexing

hashmap