程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode 205 Isomorphic Strings(同構的字符串)(string、vector、map)(*)

LeetCode 205 Isomorphic Strings(同構的字符串)(string、vector、map)(*)

編輯:關於C++

翻譯

給定兩個字符串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;
    }
};
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved