LeetCode #205 字串是否同構

Klook.com
文章觀看次數: 281

英文原文如下

Given two strings s and t, determine if they are isomorphic.

Two strings s and t 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.

中文翻譯

給予兩個字串 s 跟 t，確認他們是否為同構(*)

要確認兩個字串 s 跟 t 是否為同構 ，那就是每個 s 中的字元可以被替換然後等於 t

必須將一個字元的所有出現都替換成另一個字元，同時保持它們的順序。兩個字元不能映射到相同的字元，但一個字符可以映射到它自己。

範例及題目限制

解題思路

在查看了這個問題的描述之後，我立刻發現我前幾天寫過類似的

看這個 ➡ LeetCode #290 Word Pattern 單詞樣板(模式)

唯一的差異在於其中一個問題是字元對應到字串，而這一次的則是字元對應字元

在這個問題中，兩個字串已經被定義為相同的長度，所以可以省略相等長度的要求

因此，我們可以微調答案就能獲得答案了!!

C# 解決方案

方案1

public class Solution {
    public bool IsIsomorphic(string s, string t) {
        Dictionary<char,char> dict =   new Dictionary<char,char>();
        HashSet<char> hSet = new HashSet<char>();

        for(int i = 0; i< s.Length;i++)
        {
            var sChar = s[i];
            var tChar = t[i];
            if (!dict.ContainsKey(sChar))
            {
                if(hSet.Contains(tChar))
                {
                    return false;
                }
                dict.Add(sChar, tChar);
                hSet.Add(tChar);
            }
            else    //check if exists
            {
                if(tChar != dict[sChar])
                {
                    return false;
                }
            }
        }

        return true;
    }
}

一樣用到了Dictionary以及HashSet

前者用來儲存對應表，後者則是用來判斷替換字元是否已經被用過了(兩個不同的字元不能對應到同個字元上!!)

Java解決方案

方案1

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> dict =   new HashMap<Character,Character>();
        HashSet<Character> hSet = new HashSet<Character>();

        for(int i = 0; i< s.length();i++)
        {
            var sChar = s.charAt(i);
            var tChar = t.charAt(i);
            if (!dict.containsKey(sChar))
            {
                if(hSet.contains(tChar))
                {
                    return false;
                }
                dict.put(sChar, tChar);
                hSet.add(tChar);
            }
            else    //check if exists
            {
                if(tChar != dict.get(sChar))
                {
                    return false;
                }
            }
        }

        return true;
    }
}

Python3 解決方案

方案1

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        dict = {}
        hSet = set()

        for i in range (len(s)):
            sChar = s[i]
            tChar = t[i]
            if (sChar not in dict):
                if(tChar in hSet):
                    return False
                
                dict[sChar] = tChar
                hSet.add(tChar)
            
            else:    #check if exists
                if(tChar != dict[sChar]):
                    return False

        return True

JavaScript 解決方案

方案1

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
    const dict = new Map();
    const hSet = new Set();

    for(let i = 0; i< s.length;i++)
    {
        const sChar = s.charAt(i);
        const tChar = t.charAt(i);
        if (!dict.has(sChar))
        {
            if(hSet.has(tChar))
            {
                return false;
            }
            dict.set(sChar, tChar);
            hSet.add(tChar);
        }
        else    //check if exists
        {
            if(tChar !== dict.get(sChar))
            {
                return false;
            }
        }
    }

    return true;
};

結論

寫過越多問題，下次遇到類似的就可以很容易想到該怎麼處理了

(當然，記憶力不好的話還是偶爾要做做筆記)

參考 :

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Isomorphic Strings – LeetCode

其他的LeetCode文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *