638.Strings Homomorphism

1.Description(Easy)

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Notice

You may assume both s and t have thesame length.

Example

Given s ="egg", t ="add", returntrue.

Given s ="foo", t ="bar", returnfalse.

Given s ="paper", t ="title", returntrue.

Tags

LinkedIn Hash Table

2.Code

Solution 1:

判断对应位置字符是否成唯一映射，同时判断是否出现重复映射。

public boolean isIsomorphic(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        HashMap<Character,Character> map=new HashMap<Character,Character>();
        HashSet<Character> set=new HashSet<Character>();
        for(int i=0;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                //如果map中没有s的值，但是set中已经出现了，就说明出现了重复映射。
                if(set.contains(t.charAt(i))){
                    return false;
                }
                map.put(s.charAt(i),t.charAt(i));
                set.add(t.charAt(i));
            }
            else{
                if(map.get(s.charAt(i))!=t.charAt(i)){
                    return false;
                }
            }
        }
        return true;
    }

Solution 2:

public boolean isIsomorphic(String s, String t) {
        // Write your code here
        int[] m1 = new int[128];
        int[] m2 = new int[128];
        for (int i = 0; i < s.length(); ++i) {
            int cs = (int) s.charAt(i);
            int ts = (int) t.charAt(i);
            if (m1[cs] == 0 && m2[ts] == 0) {
                m1[cs] = ts;
                m2[ts] = 1;
            } else if (m1[cs] != ts) {
                return false;
            }
        }
        return true;
    }