LeetCode 205 Isomorphic Strings（同構的字符串）（string、vector、map）（*）

LeetCode 205 Isomorphic Strings（同構的字符串）（string、vector、map）（*）

翻譯

給定兩個字符串s和t，決定它們是否是同構的。

如果s中的元素被替換可以得到t，那麼稱這兩個字符串是同構的。

在用一個字符串的元素替換另一個字符串的元素的過程中，所有字符的順序必須保留。
沒有兩個字符可以被映射到相同的字符，但字符可以映射到該字符本身。

例如，
給定“egg”，“add”，返回真。
給定“foo”，“bar”，返回假。
給定“paper”，“title”，返回真。

批注：
你可以假設s和t有相同的長度。

原文

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. 
No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

分析

翻譯完這題目就很自然的想到一個方法，我希望將字符串全部輸出成數字序列：

For example,

Given "paper", return "01023".

Given "foo", return "011".

Given "isomorphic", return "0123245607".

於是就將這個功能給實現了：

vector getVecOrder(string str) {
    map strM;
    int index = 0;
    vector strVec;
    for (int i = 0; i < str.size(); ++i) {
        auto iter = strM.find(str[i]);
        if (iter == strM.end()) {
            strM.insert(pair(str[i], index));
            strVec.push_back(index);
            index += 1;
        }
        else {
            strVec.push_back(strM[str[i]]);
        }
    }
    return strVec;
}

這裡用map來保存每個字符和索引的鍵值對，索引用index來表示，索引從0開始。

最後的數字序列用vector來保存。

循環遍歷整個字符串，每次在map中尋找一個字符，如果沒有找到，則將其和對應的index添加進去，如果已經存在，就將該字符的索引從map中獲取出來並添加到vector中。

有了這個模塊函數，解起題來就輕而易舉咯：

bool isIsomorphic(string s, string t) {
    vector v_s = getVecOrder(s), v_t = getVecOrder(t);
    for (int i = 0; i < v_s.size(); ++i) {
        if (v_s[i] != v_t[i]) return false;
    }                                                  
    return true;
}

因為字符串的長度題目說了是等長的，所以vector的長度肯定也是相等的了。

代碼

class Solution {
public:
    vector getVecOrder(string str) {
        int len = str.size();
        map strM;
        int index = 0;
        vector strVec;
        for (int i = 0; i < len; ++i) {
            auto iter = strM.find(str[i]);
            if (iter == strM.end()) {
                strM.insert(pair(str[i], index));
                strVec.push_back(index);
                index += 1;
            }
            else {
                strVec.push_back(strM[str[i]]);
            }
        }
        return strVec;
    }

    bool isIsomorphic(string s, string t) {
        vector v_s = getVecOrder(s), v_t = getVecOrder(t);
        for (int i = 0; i < v_s.size(); ++i) {
            if (v_s[i] != v_t[i]) return false;
        }
        return true;
    }
};