[LeetCode] 205. Isomorphic Strings 同構(gòu)字符串

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.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar" Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

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

這道題讓我們求同構(gòu)字符串，就是說原字符串中的每個字符可由另外一個字符替代，可以被其本身替代，相同的字符一定要被同一個字符替代，且一個字符不能被多個字符替代，即不能出現(xiàn)一對多的映射。根據(jù)一對一映射的特點，需要用兩個 HashMap 分別來記錄原字符串和目標(biāo)字符串中字符出現(xiàn)情況，由于 ASCII 碼只有 256 個字符，所以可以用一個 256 大小的數(shù)組來代替 HashMap，并初始化為0，遍歷原字符串，分別從源字符串和目標(biāo)字符串取出一個字符，然后分別在兩個數(shù)組中查找其值，若不相等，則返回 false，若相等，將其值更新為 i + 1，因為默認的值是0，所以更新值為 i + 1，這樣當(dāng) i=0 時，則映射為1，如果不加1的話，那么就無法區(qū)分是否更新了，代碼如下：

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(205.同構(gòu)字符串)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)同構(gòu)字符串內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論