LeetCode 205：判斷同構字符串（映射編碼法）

題目描述

給定兩個字符串 s 和 t，判斷它們是否同構。若 s 中字符可被替換得到 t，且字符順序保持不變，且無兩字符映射到同一字符，則稱同構。例如 "egg" 和 "add" 同構，"foo" 和 "bar" 不同構。

解題思路

將字符串轉換為數字序列：首次出現的字符分配遞增索引，後續相同字符使用相同索引。若兩字符串生成的數字序列完全一致，則同構。使用 map<char, int> 記錄字符到索引的映射，vector<int> 存儲序列。

核心函數

vector<int> getVecOrder(string str) {
    map<char, int> strMap;
    int index = 0;
    vector<int> vec;
    for (char c : str) {
        auto it = strMap.find(c);
        if (it == strMap.end()) {
            strMap[c] = index;
            vec.push_back(index);
            ++index;
        } else {
            vec.push_back(it->second);
        }
    }
    return vec;
}

完整解法

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> v1 = getVecOrder(s);
        vector<int> v2 = getVecOrder(t);
        return v1 == v2;
    }

private:
    vector<int> getVecOrder(string str) {
        map<char, int> m;
        int idx = 0;
        vector<int> res;
        for (char c : str) {
            if (!m.count(c)) m[c] = idx++;
            res.push_back(m[c]);
        }
        return res;
    }
};

複雜度

• 時間：O(n)，n 為字符串長度。
• 空間：O(n)，存儲映射與序列。