LeetCode 205、同构字符串

一、题目描述

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add" 输出：true

示例 2：

输入：s = "foo", t = "bar" 输出：false

示例 3：

输入：s = "paper", t = "title" 输出：true

提示：

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

二、题目解析

三、参考代码

Python

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:

        # 设置一个哈希集合用来存储字符串 s 当中的元素
        dic1 = {}

        # 设置一个哈希集合用来存储字符串 t 当中的元素
        dic2 = {}

        # 由于 t.length == s.length
        # 按照顺序访问 s 和 t 中对应的元素
        for i in range(len(s)):

            # 1、访问的元素 s[i] 存在于 dic1 中
            # 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
            # 返回 False
            if s[i] in dic1 and dic1[s[i]] != t[i]:
                return False

            # 2、访问的元素 t[i] 存在于 dic2 中
            # 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
            # 返回 False
            if t[i] in dic2 and dic2[t[i]] != s[i]:
                return False

            # 3、访问的元素 s[i] 不存在于 dic1 中
            # 存放到哈希集合中
            if s[i] not in dic1:
                # dic1[s[i]] = t[i]
                dic1[s[i]] = t[i]

            # 3、访问的元素 t[i] 不存在于 dic2 中
            # 存放到哈希集合中
            if t[i] not in dic2:
                # dic2[t[i]] = s[i]
                dic2[t[i]] = s[i]
        # 返回 True
        return True

Java

class Solution {
    public boolean isIsomorphic(String s, String t) {

        // 设置一个哈希集合用来存储字符串 s 当中的元素
        HashMap<Character, Character> dic1 = new HashMap<>();

        // 设置一个哈希集合用来存储字符串 t 当中的元素
        HashMap<Character, Character> dic2 = new HashMap<>();

        // 由于 t.length == s.length
        // 按照顺序访问 s 和 t 中对应的元素
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);

            // 1、访问的元素 s[i] 存在于 dic1 中
            // 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
            // 返回 false
            if (dic1.containsKey(sChar) && dic1.get(sChar) != tChar) {
                return false;
            }

            // 2、访问的元素 t[i] 存在于 dic2 中
            // 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
            // 返回 false
            if (dic2.containsKey(tChar) && dic2.get(tChar) != sChar) {
                return false;
            }

            // 3、访问的元素 s[i] 不存在于 dic1 中
            // 存放到哈希集合中
            if (!dic1.containsKey(sChar)) {
                dic1.put(sChar, tChar);
            }

            // 3、访问的元素 t[i] 不存在于 dic2 中
            // 存放到哈希集合中
            if (!dic2.containsKey(tChar)) {
                dic2.put(tChar, sChar);
            }
        }
        // 返回 true
        return true;
    }
}

C++

class Solution {
public:
    bool isIsomorphic(string s, string t) {

        // 设置一个哈希集合用来存储字符串 s 当中的元素
        unordered_map<char, char> dic1;

        // 设置一个哈希集合用来存储字符串 t 当中的元素
        unordered_map<char, char> dic2;

        // 由于 t.length == s.length
        // 按照顺序访问 s 和 t 中对应的元素
        for (int i = 0; i < s.size(); i++) {
            char sChar = s[i];
            char tChar = t[i];

            // 1、访问的元素 s[i] 存在于 dic1 中
            // 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
            // 返回 false
            if (dic1.count(sChar) && dic1[sChar] != tChar) {
                return false;
            }

            // 2、访问的元素 t[i] 存在于 dic2 中
            // 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
            // 返回 false
            if (dic2.count(tChar) && dic2[tChar] != sChar) {
                return false;
            }

            // 3、访问的元素 s[i] 不存在于 dic1 中
            // 存放到哈希集合中
            if (!dic1.count(sChar)) {
                dic1[sChar] = tChar;
            }

            // 3、访问的元素 t[i] 不存在于 dic2 中
            // 存放到哈希集合中
            if (!dic2.count(tChar)) {
                dic2[tChar] = sChar;
            }
        }
        // 返回 true
        return true;
    }
};

C

#include <stdbool.h>
#include <string.h>

bool isIsomorphic(char *s, char *t) {
    // 创建两个映射数组，用于存储字符的映射关系
    char mapS[256] = {0};
    char mapT[256] = {0};

    // 遍历字符串 s 和 t 的每个字符
    for (int i = 0; s[i] != '\0'; i++) {
        char chS = s[i];
        char chT = t[i];

        // 如果 s 的字符已经映射，但映射的字符不匹配 t 的当前字符
        if (mapS[chS] && mapS[chS] != chT) {
            return false;
        }

        // 如果 t 的字符已经映射，但映射的字符不匹配 s 的当前字符
        if (mapT[chT] && mapT[chT] != chS) {
            return false;
        }

        // 建立双向映射
        mapS[chS] = chT;
        mapT[chT] = chS;
    }

    // 若无冲突，返回 true
    return true;
}

Node JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
    // 创建两个哈希表，用于存储字符的映射关系
    const mapS = new Map();
    const mapT = new Map();

    // 遍历字符串 s 和 t 的每个字符
    for (let i = 0; i < s.length; i++) {
        const chS = s[i];
        const chT = t[i];

        // 如果 s 的字符已经映射，但映射的字符不匹配 t 的当前字符
        if (mapS.has(chS) && mapS.get(chS) !== chT) {
            return false;
        }

        // 如果 t 的字符已经映射，但映射的字符不匹配 s 的当前字符
        if (mapT.has(chT) && mapT.get(chT) !== chS) {
            return false;
        }

        // 建立双向映射
        mapS.set(chS, chT);
        mapT.set(chT, chS);
    }

    // 若无冲突，返回 true
    return true;
};

Go

func isIsomorphic(s string, t string) bool {
    // 创建两个映射数组，用于存储字符的映射关系
    mapS := make(map[byte]byte)
    mapT := make(map[byte]byte)

    // 遍历字符串 s 和 t 的每个字符
    for i := 0; i < len(s); i++ {
        chS := s[i]
        chT := t[i]

        // 如果 s 的字符已经映射，但映射的字符不匹配 t 的当前字符
        if val, exists := mapS[chS]; exists && val != chT {
            return false
        }

        // 如果 t 的字符已经映射，但映射的字符不匹配 s 的当前字符
        if val, exists := mapT[chT]; exists && val != chS {
            return false
        }

        // 建立双向映射
        mapS[chS] = chT
        mapT[chT] = chS
    }

    // 若无冲突，返回 true
    return true
}