Leetcode 同构字符串

这道题的意思，其实就是要求，从s->t和从t->s这两个单向映射只要重复的字符映射关系保持一致就okay，所以我们需要创建2个哈希表。
是的，你理解得很正确！这道题的核心要求就是确保两个字符串之间的映射关系是一致且唯一的。也就是说：

1. 从 s -> t 的映射中，每个字符在 s 中出现的位置映射到 t 中的字符时，保持一致。
2. 从 t -> s 的映射中，每个字符在 t 中出现的位置映射回 s 时，也保持一致。

换句话说

• 如果 s 中的某个字符多次出现在相同的位置上，那么它必须始终映射到 t 中同一位置的字符。
• 同样地，如果 t 中的某个字符多次出现在相同的位置上，那么它必须始终映射到 s 中同一位置的字符。

举例说明

• 比如 s = "egg" 和 t = "add"：

  • 从 s -> t：e -> a，g -> d，且每个 g 都对应 d，符合要求。
  • 从 t -> s：a -> e，d -> g，且每个 d 都对应 g，符合要求。

• 如果 s = "foo" 和 t = "bar"：

  • 从 s -> t：f -> b，o -> a（但是遇到 o 时，再次对应 a，符合要求）。
  • 从 t -> s：b -> f，a -> o，但 r -> o，不一致，不满足同构条件。

总结

所以，这道题的要求确实可以归结为：在 s -> t 和 t -> s 的双向映射中，每个重复字符的映射关系要保持一致。通过两个哈希表的方式可以帮助我们准确地检测这种一致性。

算法的基本思想是使用两个哈希映射来建立字符的双向映射关系，并检查两个字符串是否满足同构条件。以下是详细的解释：

算法思想

1. 建立双向映射：我们使用两个哈希映射 mapS 和 mapT，分别用于存储 s 到 t 的映射关系和 t 到 s 的映射关系。这是因为如果字符串 s 中的字符可以映射到 t 中的字符，那么 t 中的字符也应该唯一地映射到 s 中的字符。

2. 逐字符检查映射关系：

   • 遍历字符串 s 和 t，对每一对对应位置的字符 c1（来自 s）和 c2（来自 t）进行检查。
   • 检查 c1 在 mapS 中是否已经存在映射关系：
     • 如果存在，则判断当前字符 c1 的映射值是否为 c2，如果不是，说明映射冲突，返回 false。
     • 如果不存在，则将 c1 和 c2 的映射关系添加到 mapS 中。
   • 同样，检查 c2 在 mapT 中的映射关系：
     • 如果存在，则判断当前字符 c2 的映射值是否为 c1，如果不是，说明映射冲突，返回 false。
     • 如果不存在，则将 c2 和 c1 的映射关系添加到 mapT 中。

3. 返回结果：如果遍历完整个字符串都没有出现映射冲突，说明两个字符串是同构的，返回 true。

时间复杂度

由于我们只对字符串 s 和 t 进行一次线性扫描，每次扫描的操作都是常数时间的映射查找和插入操作，因此算法的时间复杂度为 (O(n))，其中 (n) 是字符串的长度。

示例

对于输入 s = "egg" 和 t = "add"：

• 第一次循环：c1 = 'e'，c2 = 'a'，建立 'e' -> 'a' 和 'a' -> 'e' 的双向映射。
• 第二次循环：c1 = 'g'，c2 = 'd'，建立 'g' -> 'd' 和 'd' -> 'g' 的双向映射。
• 第三次循环：c1 = 'g'，c2 = 'd'，检查发现映射关系一致，继续。

没有冲突，返回 true。

通过这种方法，我们能够有效地判断两个字符串是否同构。

java 实现

class Solution {
    public boolean isIsomorphic(String s, String t) {
        //这道题目的要求是，从s->t和从t->s这两个单向映射只要重复的字符映射关系保持一致就okay
        //首先针对特殊情况进行处理
        //如果s和t的长度都不一致,那肯定不是同构的
        if(s.length() != t.length()) return false;

        //然后创建哈希表
        Map<Character, Character> mapS = new HashMap<>();
        Map<Character, Character> mapT = new HashMap<>();

        //遍历两个字符串
        for(int i = 0; i < s.length(); ++i) {
            //先分别获取s和t的当前字符
            char a = s.charAt(i);
            char b = t.charAt(i);

            if(mapS.containsKey(a)) {//如果哈希表S中已经存在了当前的s字符
                //判断当前的t字符是否和哈希表中的值一致,如果不一致直接返回false
                if(mapS.get(a) != b) return false;
            }else {
                mapS.put(a, b);
            }

            if(mapT.containsKey(b)) {//如果哈希表T中已经存在了当前的t字符
                //判断当前的s字符是否和哈希表中的值一致,如果不一致直接返回false
                if(mapT.get(b) != a) return false;
            }else {
                mapT.put(b, a);
            }

        }
        return true;
        
    }
}