220 字
1 分钟
LeetCode 面试经典150题 [39/150 同构字符串]
题目描述
给定两个字符串 s 和 t ，判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。 示例 1：
输入：s = "egg", t = "add"输出：true示例 2：
输入：s = "foo", t = "bar"输出：false示例 3：
输入：s = "paper", t = "title"输出：true个人C++解答
时间复杂度较高，待优化，可以多开一个哈希表，省去每次的从头遍历查找
class Solution {public: bool isIsomorphic(string s, string t) { unordered_map<char, char> Map; int index = 0, flag = 0; for (auto s_ : s) { flag = 0; for (auto pair : Map) { if (pair.second == t[index]) { flag = 1; if (Map.find(s_) != Map.end()) { if (Map[s_] == t[index]) { break; } else { return false; } } else { return false; } } } if (flag == 0) { if (Map.find(s_) == Map.end()) { Map[s_] = t[index]; } else if (Map[s_] == t[index]) {
} else { return false; } } index++; } return true; }};优化代码
此次优化增大的内存开销，时间上没有太大的提升，但是代码更简洁了
class Solution {public: bool isIsomorphic(string s, string t) { unordered_map<char, char> sMap; unordered_map<char, char> tMap; for (int i = 0; i < s.size(); i++) { if (sMap.count(s[i])) { if (sMap[s[i]] != t[i]) { return false; } } else { if (tMap.count(t[i])) { if (tMap[t[i]] != s[i]) { return false; } } tMap[t[i]] = s[i]; sMap[s[i]] = t[i]; } } return true; }}; 分享
如果这篇文章对你有帮助，欢迎分享给更多人！
LeetCode 面试经典150题 [39/150 同构字符串]
https://ericonline.cn/posts/leetcode-面试经典150题-39-150-同构字符串/ 部分信息可能已经过时
相关文章 智能推荐