Isomorphic Strings

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.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Note: You may assume boths andt have the same length.

Analysis

其中有一个注意点是不同的character不能map到相同的character，相同的character要map到同一个character，也就是要满足一一对应的mapping关系。

Map to Index

把s，t中的对应字符map到相同的数字，而不是直接map在s，t中的对应字符。空间上只需要开辟两个ASCII大小的char数组，一次遍历即可发现，如果有map到不同数字就返回false。

@grandyang

The idea is that we need to map a char to another one, for example, "egg" and "add", we need to constract the mapping 'e' -> 'a' and 'g' -> 'd'. Instead of directly mapping 'e' to 'a', another way is to mark them with same value, for example, 'e' -> 1, 'a'-> 1, and 'g' -> 2, 'd' -> 2, this works same.

So we use two arrays here m1 and m2, initialized space is 256 (Since the whole ASCII size is 256, 128 also works here). Traverse the character of both s and t on the same position, if their mapping values in m1 and m2 are different, means they are not mapping correctly, returen false; else we construct the mapping, since m1 and m2 are both initialized as 0, we want to use a new value when i == 0, so i + 1 works here.

做了一些微小修改，初始化sarr, tarr为-1，这样直接assign i就可以，而不用i+1

10 ms 77.19%

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length())
            return false;

        int[] sarr = new int[256];
        int[] tarr = new int[256];
        Arrays.fill(sarr, -1);
        Arrays.fill(tarr, -1);

        for (int i = 0; i < s.length(); i++) {
            if (sarr[s.charAt(i)] != tarr[t.charAt(i)])
                return false;
            sarr[s.charAt(i)] = i;
            tarr[t.charAt(i)] = i;
        }

        return true;
    }
}

Map between Character

HashMap + HashSet

HashMap存s -> t中字符映射关系

HashSet 检测是否有重复mapping，即 'a' -> 'b', 'b' -> 'b'这样的情形

25 ms, faster than 31.37%

public boolean isIsomorphic(String s, String t) {
        if (s.length != t.length()) {
            return false;
        }
        Map<Character,Character> map=new HashMap<>();
        Set<Character> set=new HashSet<>();

        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 (set.contains(t.charAt(i))) {
                    return false;
                }
                map.put(s.charAt(i), t.charAt(i));
                set.add(t.charAt(i));
            }
        }
        return true;
    }

Map ContainsValue (NOT RECOMMENDED)

This solution is O(N*N), because of the containsValue() method! Every search of containsValue() is O(N).

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if(s == null || s.length() <= 1) return true;
        HashMap<Character, Character> map = new HashMap<Character, Character>();
        for(int i = 0 ; i< s.length(); i++){
            char a = s.charAt(i);
            char b = t.charAt(i);
            if(map.containsKey(a)){
                 if(map.get(a).equals(b))
                continue;
                else
                return false;
            }else{
                if(!map.containsValue(b))
                map.put(a,b);
                else return false;

            }
        }
        return true;

    }
}