力扣经典150题第四十题：同构字符串

用户8589624

发布于 2025-11-13 16:05:00

180

文章被收录于专栏：nginxnginx

力扣经典150题第四十题：同构字符串

引言

本篇博客介绍了力扣经典150题中的第四十题：同构字符串。题目要求判断两个字符串 s 和 t 是否是同构的。

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

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

题目详解

给定两个字符串 s 和 t，要求判断它们是否是同构的。示例1:

输入: pattern = “abba”, s = “dog cat cat dog” 输出: true 示例 2:

输入:pattern = “abba”, s = “dog cat cat fish” 输出: false 示例 3:

输入: pattern = “aaaa”, s = “dog cat cat dog” 输出: false

解题思路

为了判断两个字符串 s 和 t 是否同构，可以通过建立字符到字符的映射关系，然后进行验证。

具体步骤如下：

使用两个哈希表 s2t 和 t2s 分别记录 s 到 t 的字符映射关系和 t 到 s 的字符映射关系。
遍历字符串 s 和 t 的每个字符，分别建立字符的映射关系。
- 如果 s 中的字符已经存在于 s2t 中，并且对应的映射不是当前字符 t 中的字符，则返回 false。
- 如果 t 中的字符已经存在于 t2s 中，并且对应的映射不是当前字符 s 中的字符，则返回 false。
- 否则，建立字符之间的映射关系。
如果遍历完成没有发现不符合映射规则的情况，则返回 true。

通过上述步骤，可以判断两个字符串 s 和 t 是否同构。

代码实现

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

public class IsomorphicStrings {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Character> s2t = new HashMap<>();
        Map<Character, Character> t2s = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);

            if (s2t.containsKey(charS) && s2t.get(charS) != charT) {
                return false;
            }

            if (t2s.containsKey(charT) && t2s.get(charT) != charS) {
                return false;
            }

            s2t.put(charS, charT);
            t2s.put(charT, charS);
        }

        return true;
    }

    public static void main(String[] args) {
        IsomorphicStrings solution = new IsomorphicStrings();

        // 示例测试
        String s1 = "egg";
        String t1 = "add";
        System.out.println("s: " + s1 + ", t: " + t1);
        System.out.println("结果: " + solution.isIsomorphic(s1, t1));

        String s2 = "foo";
        String t2 = "bar";
        System.out.println("s: " + s2 + ", t: " + t2);
        System.out.println("结果: " + solution.isIsomorphic(s2, t2));

        String s3 = "paper";
        String t3 = "title";
        System.out.println("s: " + s3 + ", t: " + t3);
        System.out.println("结果: " + solution.isIsomorphic(s3, t3));
    }
}