Isomorphic_Strings.md

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.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Code:

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map hm_s2t = new HashMap();
        Map hm_t2s = new HashMap();
        boolean res = true;
        
        for (int i = 0; i < s.length(); i++) {
            char c_s = s.charAt(i), c_t = t.charAt(i);
            if (!hm_s2t.containsKey(c_s)) {
                hm_s2t.put(c_s, c_t);
            }
            if (!hm_t2s.containsKey(c_t)) {
                hm_t2s.put(c_t, c_s);
            }
            if (hm_s2t.containsKey(c_s) && hm_s2t.get(c_s) != c_t) res = false;
            if (hm_t2s.containsKey(c_t) && hm_t2s.get(c_t) != c_s) res = false;
        }
        return res;
    }
}

---

• 该题的解题思路是将s->t以及t->s的对应字符存入HashMap；
• 对于两个字符串遍历，若某元素不存在于HashMap，则加入< s.charAt(i), t.charAt(i) >;
• 若某元素存在于HashMap中，找到对应替换元素，若不等于另一个字符串中的字符，则令返回值为false；
• 注意：要分别判断s->t以及t->s两种情况。

###改进代码：

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

---

• 用256位数组表示ASCII码表