iT邦幫忙

2024 iThome 鐵人賽

0
佛心分享-刷題不只是刷題

刷經典 LeetCode 題目系列 第 74

經典LeetCode 205. Isomorphic Strings

  • 分享至 

  • xImage
  •  

在這題我們需要判斷兩個字串 st 是否是 isomorphic。

題目:

  1. 兩個字串長度相等。
  2. s 中每個字元能唯一映射到 t 的某個字元。
  3. 同時,t 中的每個字元也只能唯一映射回 s 中的某個字元。

解題思路

如果 s 跟 t 可以映射到同一種關係上的話,那表示 s 與 t 為 isomorphic,

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size())
            return false;

        int scount = 0;
        int tcount = 0;
        unordered_map<char, int> smap;
        unordered_map<char, int> tmap;
        string smapstr;
        string tmapstr;
        for (int i = 0; i < s.size(); i++) {
            if (!smap.count(s[i])) {
                smap[s[i]] = scount;
                scount++;
            }
            smapstr += smap[s[i]];

            if (!tmap.count(t[i])) {
                tmap[t[i]] = tcount;
                tcount++;
            }
            tmapstr += tmap[t[i]];
        }

        return smapstr == tmapstr;
    }
};

後來發現可以優化空間複雜度,省去兩個 string 的開銷,因為是按順序,所以有不一樣的就提前回傳 fasle,否則直到最後就是一樣 return true。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size())
            return false;

        int scount = 0;
        int tcount = 0;
        unordered_map<char, int> smap;
        unordered_map<char, int> tmap;
        for (int i = 0; i < s.size(); i++) {
            if (!smap.count(s[i])) {
                smap[s[i]] = scount;
                scount++;
            }

            if (!tmap.count(t[i])) {
                tmap[t[i]] = tcount;
                tcount++;
            }

            if (smap[s[i]] != tmap[t[i]])
                return false;
        }

        return true;
    }
};

也可以用雙映射的方式,從 s 映射到 t 的,從 t 映射到 s ,來判斷是不是 isomorphic。

參考:
#205. Isomorphic Strings


上一篇
經典LeetCode 392. Is Subsequence
下一篇
經典LeetCode 290. Word Pattern
系列文
刷經典 LeetCode 題目80
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言