每日算法题 17---205.同构字符串

题目

205.同构字符串

要求

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

示例

示例 1：

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

输出：true

解释：

字符串s和t可以通过以下方式变得相同：将'e'映射为'a'。将'g'映射为'd'。

示例 2：

输入：s = "f11", t = "b23"

输出：false

解释：

字符串s和t无法变得相同，因为'1'需要同时映射到'2'和'3'。

思路1（哈希表）

通过题意可知，我们需要判断每个位置上的字符是否都一一对应，即 s 的任意一个字符和 t 中唯一的字符对应，同时 t 的任意一个字符被s中的唯一字符对应（一一映射）

我们想到用两个哈希表来实现，第一张哈希表 s2t 以 s 中字符为键，映射到 t 对应的字符为值，相反第二章哈希表 t2s 以 t 对应的字符为键，映射到 s 对应的字符为值。从左到右遍历两个字符串的字符，不断更新两张哈希表，如果出现不一致情况（例如：s中一个字符对应t中两个字符），就说明两个字符串无法同构；如果遍历完没有发生冲突，那么说明两个字符串同构

代码1

class Solution { public boolean isIsomorphic(String s, String t) { Map<Character, Character> s2t = new HashMap<Character, Character>(); Map<Character, Character> t2s = new HashMap<Character, Character>(); int len = s.length(); for (int i = 0; i < len; ++i) { char x = s.charAt(i), y = t.charAt(i); if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) { return false; } s2t.put(x, y); t2s.put(y, x); } return true; } }

思路2（数组）

定义两个数组来记录字符出现的位置，如果遍历到 s 和 t 的字符是新字符，那么就在对应的位置（char本质是一个整数，每个字符都有着自己的ASCII 码，相应位置坐标就是对应的ASCII 码，相应位置元素初始值为 0）元素+1，如果是记录过的字符，对应的位置元素值相等那说明上一次出现位置相同，并更新位置元素+1；对应的位置元素值不相等说明一个字符对应了两个不同的字符

来举个例子更方便理解：第一个例子：egg->add；第二个例子：foo->baf

代码2

class Solution { public boolean isIsomorphic(String s, String t) { if (s.length() != t.length()) return false; int[] sRecent = new int[250]; int[] tRecent = new int[250]; for (int i = 0; i < s.length(); i ++) { char sc = s.charAt(i); char tc = t.charAt(i); if (sRecent[sc] != tRecent[tc]) return false; sRecent[sc] = i+1; tRecent[tc] = i+1; } return true; } }

小舟有话说

如果喜欢的话，点点关注，下次不迷路~