638. 字符同构哈希映射

给定两个字符串 s 和 t ,确定它们是否是同构的。 两个字符串是同构的如果 s 中的字符可以被替换得到 t。 所有出现的字符必须用另一个字符代替,同时保留字符串的顺序。 没有两个字符可以映射到同一个字符,但一个字符可以映射到自己。

样例 给出 s = "egg", t= "add", 返回 true。 给出 s = "foo", t= "bar", 返回 false。 给出 s = "paper", t= "title", 返回 true。

哈希映射

用两个哈希表分别来存放两个字符串每个字符出现的次数,存放的过程中检查同一位置(字符串同一位置)的字符在两个哈希表中的出现的次数是否相等,如果不想等,则肯定不能同构,如果所有的都满足相等,则可同构。 这个算法的思路不是我想出来的,见这里,理解了好一会儿才明白。

因为是一一映射,所以这样遍历过来的话,两个哈希表的值增加,那么肯定最后得到的对应位置的值肯定是相等的,比如说建立的哈希表是ss<char,int>tt<char,int>,如果是s中的B和t中的C映射,那么每一步遍历中都应该有ss[B]=tt[C],因为s中出现一次B,t中也出现一次C,而且必须是立即出现(遍历到这一步就出现)。 画个图看一下:

算法示意

如果不对应映射的话可以改一个字母重复上面的过程,会更理解一些。

用map直接来做。

bool isIsomorphic(string s, string t)
    {
        int sz=s.size();
        map<char,int> ss;
        map<char,int> tt;
        for(int i=0;i<sz;i++)
        {
            ss[s[i]]++;
            tt[t[i]]++;
            if(ss[s[i]]!=tt[t[i]])
            return false;
        }
        return true;
        
    }

用数组也可以

因为字母也是存储的ascii码的,所以也可用数组来做,ascii码一共256个,可以用256的数组来做,写法基本是完全相同的,只是数组可以全部初始化为0,而map的话遇见了才添加,所以只有细微差别:

  bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; i++) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] += 1;
            m2[t[i]] += 1;
        }
        return true;
    }

这个题难的是思想,代码写起来倒是不难。重视!!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MyBlog

Effective.Java 读书笔记(4)非实例化

有时你想要编写一个类,这个类只是静态方法和静态域的组成,这样的一个类获得一个糟糕的名声因为一些人滥用他们为了避免对对象的术语进行思考,但是他们的确是有用的

9520
来自专栏LuckQI

Redis初识~Set命令

12320
来自专栏转载gongluck的CSDN博客

python笔记:#008#变量的命名

变量的命名 目标 标识符和关键字 变量的命名规则 0.1 标识符和关键字 1.1 标识符 标示符就是程序员定义的 变量名、函数名 名字 需要有 见名知义 的...

38340
来自专栏编程坑太多

js数组、json、js对象的区别与联系

35340
来自专栏take time, save time

初级程序员面试不靠谱指南(三)

二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

34090
来自专栏CDA数据分析师

Python面试中8个必考问题

1、下面这段代码的输出结果是什么?请解释。 ? 怎样修改extendList的定义能够产生以下预期的行为? 上面代码输出结果将是: ? 很多人都会误认为list...

207100
来自专栏小詹同学

Leetcode打卡 | No.27 移除元素

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

7610
来自专栏程序员同行者

python 函数进阶

函数根据 有没有参数 以及 有没有返回值,可以 相互组合,一共有 4 种 组合形式

13230
来自专栏北京马哥教育

grep命令及正则表达式

grep基本概念 grep:global search regular expression and print out the line. 作用:文本过滤器,...

37870
来自专栏liulun

Nim教程【十】

openarray类型 注意:openarray类型只能用于参数 固定大小的数组虽然性能不错,但过于呆板,使用取来不是很方便 对于一个方法来说,传入参数如果是一...

29580

扫码关注云+社区

领取腾讯云代金券