Loading... # [205. 同构字符串](https://leetcode.cn/problems/isomorphic-strings/) ## 题目 给定两个字符串 `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 * 104` - `t.length == s.length` - `s` 和 `t` 由任意有效的 ASCII 字符组成 ## 题解1 自己想的解法,就是一个 map,存储映射关系,循环遍历每个元素,分别设 s 和 t 的每个元素为 a 和 b - 如果映射表里 key 中不包含 a,且 value 中不包含 b,则写入映射表。 - 如果映射表里 key 中包含 a,则将映射值赋值为 a,并比较是否一致,如果不一致,直接返回 false。 - 如果映射表里 key 中不包含 a,但 value 中包含 b,则说明 a 之前映射为 b,现在又映射成其他的了,直接返回 false。 时间复杂度 O(n),空间复杂度 O(n). ```java class Solution { public boolean isIsomorphic(String s, String t) { Map<Character, Character> mapping = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char a = s.charAt(i); char b = t.charAt(i); if (mapping.containsKey(a)) { if (mapping.get(a) != b) { return false; } } else if (mapping.containsValue(b)) { return false; } else { mapping.put(a, b); continue; } } return true; } } ``` ## 题解 2 这个题解是在评论区找的,非常简洁的代码,另人敬佩。 思路就是,获取当前元素所在的第一个 index 是否一样,如果不一样,则说明一定有某一个元素映射此处超过 1 次。精妙绝伦。 因每次都要 indexOf 从头遍历找,故时间复杂度为 O(n²)(实际情况没有这么差,且可以利用缓存避免每次都查),空间复杂度 O(1) ```java class Solution { public boolean isIsomorphic(String s, String t) { for(int i = 0; i < s.length(); i++){ if(s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))){ return false; } } return true; } } ``` ## 题解 3 对题解 2 优化后(缓存了 index)时间复杂度 O(n),空间复杂度 O(1): ```java class Solution { public boolean isIsomorphic(String s, String t) { int[] cnt1 = new int[127]; int[] cnt2 = new int[127]; for(int i = 0; i < s.length(); i++) { char a = s.charAt(i); char b = t.charAt(i); int aa = cnt1[a]; int bb = cnt2[b]; if (aa == 0 && bb == 0) { cnt1[a] = i; cnt2[b] = i; aa = s.indexOf(a); bb = t.indexOf(b); } if (aa != bb) { return false; } } return true; } } ``` 最后修改:2022 年 08 月 30 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请我喝杯咖啡吧。