Isomorphic Strings

最后更新于:2022-04-01 22:56:21

## 一.题目描述 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. Note:  You may assume both s and t have the same length. ## 二.题目分析 这道题主要是建立两个字符串中不同字符的对应关系,由于ASCII编码的字符只有256个,而且string中是不保存null字符的,因此,可以建立两个大小为256的字符数组来保存两个string中每一个字符在另外一个string中的对应的关系,然后遍历string中的每一个字符,如果相同位置的字符是互相对应的话,就处理下一个字符,如果不是互相对应的话,就在说明这两个string不是同等结构的。 也可以通过两个map来实现,但是map的查找过程时间复杂度为O(lgn),但是上面对于string中的每一个字符串都需要查找,因此,使用map的话,时间复杂度太高了。也可以使用hash表来做,也就是使用unordered_map来实现,但是由于ASCII编码的字符的个数是固定的而且个数比较少,使用数组完全可以很好地实现。 ## 三.示例代码 ~~~ class Solution { public: bool isIsomorphic(string s, string t) { vector First(256, 0); // 创建一个含有256个0拷贝的vector vector Second(256, 0); for (size_t index = 0; index < s.size(); ++index) { unsigned char charOfFirst = s[index]; unsigned char charOfSecond = t[index]; unsigned char& First2Second = First[charOfFirst]; unsigned char& Second2First = Second[charOfSecond]; if (First2Second == 0 && Second2First == 0) { First2Second = charOfFirst; Second2First = charOfSecond; continue; } if (First2Second != 0 && Second2First != 0) { if (First2Second != charOfFirst && Second2First != charOfSecond) return false; continue; } return false; } return true; } }; ~~~ 示例结果: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5eeedbdf.jpg) ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5ef0ce41.jpg) ## 四.小结 这道题就是寻找一个好的数据结构来保存两个string之间的字符的对应关系,根据这道题的假设,选择数组是一个比较的解决方案。
';