LeetCode150道面试经典题--同构字符串(简单)

1.题目

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

2.示例/提示

---

3.思路

哈希表：

        首先两个字符串如果长度不相等，那么一定是不会一一对应的。然后一个键映射一个值，很明显就能联想到使用哈希表(HashMap)，一次遍历一个字符串，当s串中遍历时候遇到map中不存在的键并且当前的值并不对应前面的键的时候，那么就通过put方法让两者一一对应。而如果遇到存在的键时候，就需要将存在的键对应的值与当前值比较，如果不一致则返回false。如果一直没有提前返回false，则最后输出true

如果不熟悉哈希表或者忘了相关内容可以在此复习Java类集框架（二）_Alphamilk的博客-CSDN博客

4.代码

LeetCode代码：

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

时间复杂度O(n)空间复杂度O(1)

在仔细想了一下之后，没找到内存可以优化的地方，再看了一下原来大伙都是用同解

详细案例代码：

package LeetCode13;import java.util.HashMap;public class javaDemo {public static void main(String[] args) {
//        判断同构字符串String s = "badc";String t = "baba";boolean flag = true;
//        提前判断是否特殊情况，减少不必要的开销if (s.length()!=t.length()){flag = false;}
//        创建哈希表HashMap<Character,Character> map = new HashMap<>();
//        s串遍历for (int i=0;i<s.length();i++){
//            当s串当前遍历的元素并不是map中的键时候if (!map.containsKey(s.charAt(i))){
//                在不存在map的前提下，如果当前值已经被前面的键用了那么直接输出失败if (map.containsValue(t.charAt(i))){flag = false;break;}
//                否则就将键值一一对应map.put(s.charAt(i),t.charAt(i));}else {
//                当当前遍历键存在时候，则通过get得到键对应的值再与当前值比较if (map.get(s.charAt(i)) != t.charAt(i)){flag = false;break;}}}
//        最后输出结果System.out.println(flag);}
}

---