力扣205-同构字符串

一、原题题目

1.1 题目

  给定两个字符串 s 和 t ，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

1.2 示例

• 示例1：

  输入： s = "egg", t = "add"
  输出： true

• 示例2：

  输入： s = "foo", t = "bar"
  输出： false

• 示例3：

  输入： s = "paper", t = "title"
  输出： true

提示：

• 可以假设 s 和 t 长度相同。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/isomorphic-strings/

二、解题思路

2.1 利用【哈希表映射】解题

• 解题思路

  这个题比较简单，简单思考想到用哈希表来存储映射关系，用 s 中的字符作为键， t 当中对应位置的字符作为值存储，当碰到下列两种情况需要返回 false 。否则将映射加入哈希表，直到遍历完字符串返回 true 。

1.当遍历到键在哈希表中已经存在但值与 t 中对应的值不同时则返回 false 。
2.当遍历到键不在哈希表中，但 t 中对应的值在哈希表中时也要返回 false 。

• 详细代码（Java）

public boolean isIsomorphic(String s, String t) {
    if (s.length()!=t.length()) return false;
    HashMap<Character,Character> map = new HashMap<>();
    for (int i = 0;i<s.length();i++){
        if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i))!=t.charAt(i))    
          	return false;		// 上述第一种情况
        if (!map.containsKey(s.charAt(i)) && map.containsValue(t.charAt(i)))    
          	return false;		// 上述第二种情况
      	else    map.put(s.charAt(i),t.charAt(i));
    }
    return true;
}

• 代码执行结果

2.2 利用【数组映射】解题

• 解题思路

  相同上面利用哈希表的思路，这里换做用数组来保存映射关系。

• 详细代码（Java）

public boolean isIsomorphic(String s, String t) {
    int[] sTt = new int[256];			// 保存 s 到 t 的映射
    Arrays.fill(sTt, -1);					// 初试都填充为-1
    int[] tTs = new int[256];			// 保存 s 到 t 的映射
    Arrays.fill(tTs, -1);					// 初试都填充为-1
    for (int i = 0;i<s.length();i++){
      if (sTt[s.charAt(i)]!=-1&&sTt[s.charAt(i)]!=(int)(t.charAt(i))) 
        return false;		// !=-1表示已经保存过当前位置元素S到t的映射，但是保存的值与当前t中当前位置值不一样
      if (tTs[t.charAt(i)]!=-1&&tTs[t.charAt(i)]!=(int)(s.charAt(i))) 
        return false;		// !=-1表示已经保存过当前位置元素t到s的映射，但是保存的值与当前s中当前位置值不一样
      sTt[s.charAt(i)] = (int)(t.charAt(i));	// 没保存过，保存s到t的映射
      tTs[t.charAt(i)] = (int)(s.charAt(i));	// 同时保存t到s的映射
    }
    return true;
}

• 代码执行结果

2.3 利用【数组连边】解题

• 解题思路

  还是定义两个数组，为具有对应关系的字符连边并赋予权值，初始值为 0 表示未有映射关系，同为 0 才能连边。

• 详细代码（Java）

public boolean isIsomorphic(String s, String t) {
    int[] sm = new int[256];
    int[] tm = new int[256];
    for (int i = 0;i<s.length();i++){
        if (sm[s.charAt(i)]!=tm[t.charAt(i)])
          	return false;
        sm[s.charAt(i)] = tm[t.charAt(i)] = i+1;	// 连边符权值
    }
    return true;
}

• 代码执行结果