当前位置：首页 > article >正文

Leetcode 每日一题 205.同构字符串

article 2024/12/4 14:20:38

问题描述

过题图片

示例

解决方案

代码实现

题目链接

总结

问题描述

给定两个字符串 s 和 t，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。具体来说，每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

过题图片

示例

示例 1：
- 输入：s = "egg", t = "add"
- 输出：true
- 解释：s 中的 'e' 映射到 t 中的 'a'，s 中的 'g' 映射到 t 中的 'd'。
示例 2：
- 输入：s = "foo", t = "bar"
- 输出：false
- 解释：s 中的两个 'o' 不能映射到 t 中的两个不同的字符 'a' 和 'r'。
示例 3：
- 输入：s = "paper", t = "title"
- 输出：true
- 解释：s 中的 'p' 映射到 t 中的 't'，s 中的 'a' 映射到 t 中的 'i'，依此类推。

解决方案

为了解决这个问题，我们可以使用哈希表（HashMap）来存储字符之间的映射关系。以下是解决方案的详细步骤：

检查长度：首先检查两个字符串的长度是否相等。如果不相等，直接返回 false。
初始化哈希表：创建两个 HashMap，一个用于存储 s 中字符到 t 中字符的映射（mapS），另一个用于存储 t 中字符到 s 中字符的映射（mapT）。
遍历字符串：遍历字符串 s 和 t 中的每个字符。
检查映射关系：
- 如果 s 中的字符已经在 mapS 中有映射，检查这个映射是否与 t 中对应的字符相等。如果不等，返回 false。
- 如果 s 中的字符不在 mapS 中，检查 t 中的字符是否已经在 mapT 中有映射。如果有，返回 false。
- 如果 t 中的字符没有在 mapT 中映射，将 s 中的字符和 t 中的字符分别添加到 mapS 和 mapT 中。
返回结果：如果遍历结束后没有返回 false，则两个字符串是同构的，返回 true。

代码实现

java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Character> mapS = new HashMap<>();
        Map<Character, Character> mapT = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (mapS.containsKey(c1)) {
                if (mapS.get(c1) != c2) {
                    return false;
                }
            } else {
                if (mapT.containsKey(c2)) {
                    return false;
                }
                mapS.put(c1, c2);
                mapT.put(c2, c1);
            }
        }
        return true;
    }
}