Isomorphic Strings

• Easy
• tag: String, HashMap, ASCII
• Similar: word pattern, Bulls & Cows

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,
  1. Given "egg", "add", return true.
  2. Given "foo", "bar", return false.
  3. Given "paper", "title", return true.
  4. Given "aa", "ab", return false.

思路

• 简单的就是记录所有mapping记录, 然后比较有没有不符合mapping的. 注意这里是1-1映射, 但是并不是"a->b" => "b->a". 例如"ab"->"bc".
• 由于规定了是ASCII, 所以用256个元素的array也可以.

idea 1 : 使用map, 但是第27个test case出错!

• 记录每一个mapping, 只要发现不match就return false.
• 代码如下:

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

• 但是上面的代码会在"ab","aa"报错.我直接返回true了, 因为b->a并没有报错. 而事实上,由于是1-1映射, 所以不应该有a/b都map到a的. 所以就是每次有新的mapping, 都检查一下映射值是否用过了. 若用过, 说明有其他数map到这个映射值了.
• 所以修改了以上代码如下:

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

idea 2

• 由于是固定的ASCII只有256个. 所以总共是512. (因为s, t各用256个). 然后建立1-1映射关系.
• 代码如下:

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