LeetCode 力扣 205. 同构字符串

打印 上一主题 下一主题

主题 721|帖子 721|积分 2163

给定两个字符串 s 和 t ,判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
示例 1:
输入:s = "egg", t = "add"
输出:true
示例 2:
输入:s = "foo", t = "bar"
输出:false
示例 3:
输入:s = "paper", t = "title"
输出:true
思路

hash表解决单方向的映射问题,即只能保证从多对多变成多对一,因此需要翻转两次hash表才行
code
  1. class Solution {
  2. public:
  3. //hash只能 解决单方向的映射问题,即只能保证从多对多变成
  4. // 多对一,因此要来两边才行
  5.     bool isIsomorphic(string s, string t) {
  6.         //方法1:用hash记录映射关系
  7.         //方法2:用数组hash来记录映射关系
  8.         unordered_map<char,char> umap;
  9.         if(s.size() != t.size()){
  10.             return false;
  11.         }
  12.         for(int i = 0 ;i < s.size() ; i ++){
  13.             if(umap.find(s[i]) == umap.end()){
  14.                 umap.insert(make_pair(s[i],t[i]));
  15.             }else{
  16.                 if(umap[s[i]] != t[i]){
  17.                     return false;
  18.                 }
  19.             }
  20.         }
  21.         umap.clear();
  22.         swap(s,t);
  23.                 for(int i = 0 ;i < s.size() ; i ++){
  24.             if(umap.find(s[i]) == umap.end()){
  25.                 umap.insert(make_pair(s[i],t[i]));
  26.             }else{
  27.                 if(umap[s[i]] != t[i]){
  28.                     return false;
  29.                 }
  30.             }
  31.         }
  32.         return true;
  33.     }
  34. };
复制代码
本文由博客一文多发平台 OpenWrite 发布!

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

前进之路

金牌会员
这个人很懒什么都没写!

标签云

快速回复 返回顶部 返回列表