C++實現LeetCode(205.同構字符串)

Posted on by

[LeetCode] 205. Isomorphic Strings 同構字符串

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.

這道題讓我們求同構字符串，就是說原字符串中的每個字符可由另外一個字符替代，可以被其本身替代，相同的字符一定要被同一個字符替代，且一個字符不能被多個字符替代，即不能出現一對多的映射。根據一對一映射的特點，需要用兩個 HashMap 分別來記錄原字符串和目標字符串中字符出現情況，由於 ASCII 碼隻有 256 個字符，所以可以用一個 256 大小的數組來代替 HashMap，並初始化為0，遍歷原字符串，分別從源字符串和目標字符串取出一個字符，然後分別在兩個數組中查找其值，若不相等，則返回 false，若相等，將其值更新為 i + 1，因為默認的值是0，所以更新值為 i + 1，這樣當 i=0 時，則映射為1，如果不加1的話，那麼就無法區分是否更新瞭，代碼如下：

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

到此這篇關於C++實現LeetCode(205.同構字符串)的文章就介紹到這瞭,更多相關C++實現同構字符串內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：