leetcode205-同构字符串

原题

给定两个字符串 s 和 t,判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

示例1:

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

示例2:

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

示例3:

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

解法

思想

  1. 相同的字符要对应相同的字符,那么相同字符处于后位置的字符的第一次出现的位置就应该相同。
  2. 哈希表记录对应关系

代码

  1. indexOf (作者:hao-fei-hao)
class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] ch1 = s.toCharArray();
        char[] ch2 = t.toCharArray();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if(s.indexOf(ch1[i]) != t.indexOf(ch2[i])){
                return false;
            }
        }
        return true;
    }
}
  1. 哈希表
class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> map = new HashMap<>(); 
        Map<Character,Character> mapB = new HashMap<>(); 
        for(int i = 0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                if(t.charAt(i)!=map.get(s.charAt(i))) return false;
            }
            if(mapB.containsKey(t.charAt(i))){
                if(s.charAt(i)!=mapB.get(t.charAt(i))) return false;
            }
            map.put(s.charAt(i),t.charAt(i));
            mapB.put(t.charAt(i),s.charAt(i));
        }
        return true;
    }
}

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character,Character> map=new HashMap<>();
        for (int i=0;i<s.length();i++){
            if (map.containsKey(s.charAt(i))) {
                if (map.get(s.charAt(i))!=t.charAt(i)) return false;
            }else{
                //不存在对应的键但是存在对应的值
                if (map.containsValue(t.charAt(i))) return false;
                else map.put(s.charAt(i),t.charAt(i));
            }
        }
        return true;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode205-%e5%90%8c%e6%9e%84%e5%ad%97%e7%ac%a6%e4%b8%b2/