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

力扣经典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 是否同构，可以通过建立字符到字符的映射关系，然后进行验证。

具体步骤如下：

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

示例演示

展示了三个不同的示例测试，验证了字符串 s 和 t 是否同构的功能。

复杂度分析

该解法的时间复杂度为 O(n)，其中 n 是字符串 s 或 t 的长度。空间复杂度为 O(1)，因为字符集范围是 ASCII 字符，哈希表的大小是固定的。