205. Isomorphic Strings

Leetcode Hash Table

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

Example 4:

Input: s = "aa", t = "ab"
Output: false

Note: You may assume both s and t have the same length.

分析

确认字符串同构。这道题目最直接的方法是利用HashMap存放一一对应的字符。key-value之间的映射相当于字符之间的对应。当比较字符时，如果字符已经包括在Map中，则取出对应字符，对比是否相同；则否，尝试着存入字符，但字符不能已经包括在value中，不然就不是一一对应了。

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    if (s.length() == 0) return true;
    Map<Character, Character> map = new HashMap<>();
    char char1, char2;
    for (int i = 0; i < s.length(); i++) {
        char1 = s.charAt(i);
        char2 = t.charAt(i);
        // 取出字符，对比
        if (map.containsKey(char1)) {
            if (map.get(char1) != char2)
                return false;
        } else {
            // 字符存在与value中吗？
            if (map.containsValue(char2))
                return false;
            // 放入字符对
            map.put(char1, char2);
        }
    }
    return true;
}

但是map.containsValue()方法是$O(n)$的，所以最坏情况下，isIsomorphic()需要$O(n^2)$的时间复杂度，还好总共只有26个字符，所以影响不大。如果要减少map.containsValue()方法对时间复杂度的影线，可以将value值单独放在HashSet中，实现常数时间的检索。

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    if (s.length() == 0) return true;
    Map<Character, Character> map = new HashMap<>();
    Set<Character> set = new HashSet();
    char char1, char2;
    for (int i = 0; i < s.length(); i++) {
        char1 = s.charAt(i);
        char2 = t.charAt(i);
        // 取出字符，对比
        if (map.containsKey(char1)) {
            if (map.get(char1) != char2)
                return false;
        } else {
            // 字符存在与value中吗？
            if (!set.add(char2))
                return false;
            // 放入字符对
            map.put(char1, char2);
        }
    }
    return true;
}

除了存储字符的一一对应关系，还有什么方法呢？一种更快的方法是存储字符的下标。如果字符一一对应，那么存储的字符的下标一定相同。当遇到下一对字符时，我们先比较这对字符的下标，如果不同，则肯定不是同形字符串。

public boolean isIsomorphic(String s, String t) {
    int[] m1 = new int[128], m2 = new int[128];
    int index1, index2;
    for (int i = 0; i < s.length(); i++) {
        index1 = s.charAt(i);
        index2 = t.charAt(i);
        if (m1[index1] != m2[index2]) return false;
        m1[index1] = i + 1;
        m2[index2] = i + 1;
    }
    return true;
}

上面的代码用了巧妙的方法，使用数组代替哈希表直接存储字符下标。因为ascii字符只有256个，采用大小为256的数组可以代替哈希表：不仅存储及其方便，而且取值也非常快速。