力扣经典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)); } }
示例演示
展示了三个不同的示例测试，验证了字符串 s 和 t 是否同构的功能。
复杂度分析
该解法的时间复杂度为 O(n)，其中 n 是字符串 s 或 t 的长度。空间复杂度为 O(1)，因为字符集范围是 ASCII 字符，哈希表的大小是固定的。
