November 24, 2019

205. Isomorphic Strings

验证是否一对一映射 (one-to-one mapping)
abc => def: True
aba => def: False (both a is mapped to both d and f)
abc => ded: False (both a and c map to d)

最简单的方法

从左往右映射一遍，发现重复就返回false
从右往左映射一遍，发现重复就返回false

具体实现可以用两个Map做。Time=O(n), space=O(n). 也可以用一个Map做，参见290. Word Pattern做法。

思路同 290. Word Pattern

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] sMap = new int[256];
        int[] tMap = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            if (sMap[sChar] == 0) {
                sMap[sChar] = tChar;
            } 
            if (tMap[tChar] == 0) {
                tMap[tChar] = sChar;
            }
            if (sMap[sChar] != tChar || tMap[tChar] != sChar) {
                return false;
            }
        }
        return true;
    }
}