在C++中使用映射的迭代差異

我正試圖解決leetcode中的Isomorphic Strings問題。在C++中使用映射的迭代差異

我來到下面的代碼，問題是註釋塊應該像未註釋的迭代一樣運行，但它無法返回正確的答案。但是，當前的代碼可以通過測試。爲什麼區別？謝謝。

「aa」「ab」應該返回false。

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

來源

2015-10-14 Wei Guo

看起來和我完全一樣。 Ideone同意：http://ideone.com/dBVA5V –

嘗試「aa」「ab」。謝謝。 –

如果密鑰不在地圖中，您認爲'map [key]'是什麼？ –

mapped_type &操作符[]（常量爲key_type & K）; 接入元件

若k的元素的在容器中的密鑰相匹配，返回到它的映射值的參考值的功能。

如果k與容器中任何元素的鍵不匹配，則函數會使用該鍵插入一個新元素，並將其參考返回到其映射值。請注意，即使沒有爲元素分配映射值（使用其默認構造函數構造元素），也會始終將容器的大小增加1。

注意：整數的默認構造將其設置爲零。

讓我們在評論部分應用此邏輯爲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 [ '一' ] = 0，mt ['a'] = 0，比較說他們是等於。那麼它們都被設置爲i，即：0

i = 1：發現ms ['a']先前已經設置爲0，並且找不到mt ['b']但插入= 0，但是相等成功，然後兩者都設置爲1。

循環結束，成功。

問題是什麼：如果在步驟2我們發現ms [a]的值不同，測試就不會成功。

解決方案：不要在地圖中使用零作爲值。使用任何值，例如i + 10。

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

來源

2015-10-14 02:00:43

你的第一個（註釋掉）for循環將循環s.size()倍（從0到s.size()-1含）。

您的第二個for循環將循環s.size() + 1次（從s.size()到0）。

編輯：這不是你沒有通過測試的原因，但它是兩者之間的差異。

你失敗的原因是@ T.C。如果地圖不包含字符，那麼 - map [key]返回0（在你的情況下），但是你使用0作爲找到的第一個字母的值。所以你的代碼不能區分第一個字母和一個未找到的字母。

你的第二個循環工作的原因是你使用的i不是0（除了最後一個無效的迭代），所以你不會碰到第一個字母和找不到。

一個簡單的解決方案是在第一個循環中使用

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

來源

2015-10-14 01:43:20

它沒有太大的區別。 –

我明白了。非常感謝。 –

在C++中使用映射的迭代差異

回答

相關問題