leetcode205-同构字符串

彭晨涛 • 2019年12月21日 13:00 • 算法 • 阅读 18

原题

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

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

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

示例1：

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

示例2：

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

示例3：

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

解法

思想

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

代码

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;
    }
}

哈希表

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/

leetcode205-同构字符串

原题

解法

思想

代码

相关推荐

发表回复