每日算法题 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中两个字符就说明两个字符串无法同构如果遍历完没有发生冲突那么说明两个字符串同构代码1class Solution { public boolean isIsomorphic(String s, String t) { MapCharacter, Character s2t new HashMapCharacter, Character(); MapCharacter, Character t2s new HashMapCharacter, 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索引 is 字符t 字符sRecent[e]tRecent[a]判断操作0ea00相等都更新为 11gd00相等都更新为 22gd22相等都更新为 3索引 is 字符t 字符sRecent[f]tRecent[b]判断操作0fb00相等更新为 11oa00相等更新为 22or20不相等❌ 直接返回 false代码2class 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] i1; tRecent[tc] i1; } return true; } }小舟有话说如果喜欢的话点点关注下次不迷路~