Leetcode-205-同构字符串

题目描述

• 给定两个字符串 s 和 t，判断它们是否是同构的。
• 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
• 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

输入: s = "egg", t = "add"
输出: true

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true


说明:
你可以假设 s 和 t 具有相同的长度。

思路 ： 集合论双射

• 此题是「290. 单词规律」的简化版，

• 需要我们判断 s 和 t 每个位置上的字符是否都一一对应，即 s 的任意一个字符被 t中唯一的字符对应，同时 t 的任意一个字符被 s 中唯一的字符对应。这也被称为「双射」的关系。

  • 以示例 2 为例，t 中的字符 a 和 r 虽然有唯一的映射 o，但对于 s 中的字符 o 来说其存在两个映射 {a,r}，故不满足条件。

• 因此 ， 我们需要维护两张哈希表。
  • 第一张哈希表s2t : 以s中的字符为键，t中的字符为值
  • 第二张哈希表t2s : 以t中的字符为键，s中的字符为值

算法整体

1. 从左直右遍历两个字符串的字符，不断更新两张哈希表，如果出现冲突，说明两个字符无法构成同构，返回false
2. 如果遍历没有发生冲突，说明两个字符串是同构的 ， 返回true 即可。

package com.zhuuu.Leetcode__205;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class MainClass {
    public static String stringtostring(String input){
        if (input == null){
            return "null";
        }
        return input.toString();
    }

    public static String booleanToString(boolean input){
        return input?"True":"False";
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null){
            String s = stringtostring(line);
            line = in.readLine();
            String t = stringtostring(line);

            boolean ret = new Solution().isIsomorphic(s,t);
            String out = booleanToString(ret);
            System.out.println(out);
        }
    }
}


class Solution{
    public boolean isIsomorphic(String s, String t) {
        // 1. 初始化
        Map<Character,Character> s2t = new HashMap<>();
        Map<Character,Character> t2s = new HashMap<>();
        int len = s.length();

        // 2. 遍历字符串
        for(int i = 0;i < len;++i){
            // 2.1 拿到当前字符做判断
            char curr_s = s.charAt(i);
            char curr_t = t.charAt(i);
            if((s2t.containsKey(curr_s) && s2t.get(curr_s) != curr_t) || (t2s.containsKey(curr_t) && t2s.get(curr_t) != curr_s)){
                return false;
            }
            // 2.2 不在map中就放入到map中
            s2t.put(curr_s,curr_t);
            t2s.put(curr_t,curr_s);
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串的长度。我们只需同时遍历一遍字符串 s和 t 即可。

• 空间复杂度：O(∣Σ∣)，其中 \SigmaΣ 是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小，最坏情况下每个字符均不相同，需要 O(∣Σ∣) 的空间。

打赏