在 C++ 中使用 map 的迭代差异

Question

我正在尝试解决 leetcode 中的 Isomorphic Strings 问题。

我来到下面的代码，问题是注释块的功能应该与未注释的迭代相同，但它无法 return 正确答案。但是，当前代码可以通过测试。为什么不同？谢谢

"aa""ab" 应该 return 错误。

class Solution {
public:
    bool isIsomorphic(string s, string t) {

    if(s.size() != t.size())
        return false;

    map<char, int> ms;
    map<char, int> mt;

/*  for(int i = 0; i < s.size(); i++)
    {
        if(ms[s[i]] != mt[t[i]])
           return false;
        else
            ms[s[i]] = mt[t[i]] = i;
    }
*/      

    int n = s.size();
    int i = n;

    for (; i >= 0 ; --i) {
        if (ms[s[n-i]] != mt[t[n-i]])/*|| s[i] == t[i]*/
            return false;
        else
            ms[s[n-i]] = mt[t[n-i]] = i;
    }
    return true;
} 
};

Answer 1

您的第一个（注释掉的）for 循环将循环 s.size() 次（从 0 到 s.size()-1 包括在内）。

您的第二个 for 循环将循环 s.size() + 1 次（从 s.size() 到 0（含））。

编辑：这不是您未通过测试的原因，但这是两者之间的区别。

您未通过测试的原因是@T.C。说 - map[key] returns 0 （在你的情况下）如果地图不包含字符，但你使用 0 作为找到的第一个字母的值。所以您的代码无法区分第一个字母和未找到的字母。

你的第二个循环起作用的原因是你使用的 i 不是 0（除了最后一个无效的迭代），所以你不会在第一个字母和未找到。

一个简单的解决方案是使用

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

在你的第一个循环中

Answer 2

mapped_type& operator[] (const key_type& k); Access element

If k matches the key of an element in the container, the function returns a reference to its mapped value.

If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).

注意：整数的默认构造将其设置为零。

让我们将此逻辑应用于您评论部分的 s="aa" 和 t="ab"：

for(int i = 0; i < s.size(); i++)
    {
        if(ms[s[i]] != mt[t[i]])
           return false;
        else
            ms[s[i]] = mt[t[i]] = i;
    }

i = 0：两个映射都是空的，所以我们插入 ms['a'] = 0 和 mt['a'] = 0，比较说它们是相等的。然后它们都设置为 i，即：0

i = 1: 发现ms['a']之前已经设置为0，mt['b']没有找到但是inserted = 0。但是相等成功，然后两者都设置到 1.

循环结束，成功。

问题出在哪里：如果我们在第 2 步发现 ms[a] 的值不同，则测试不会成功。

解决方案：不要在地图中使用零作为值。使用任何值，例如 i+10.

ms[s[i]] = mt[t[i]] = i + 10

在 C++ 中使用 map 的迭代差异

iteration difference using map in C++

c++

string

iteration

dictionary