leetcode-205-Isomorphic Strings

题目描述:

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.

要完成的函数:

bool isIsomorphic(string s, string t) 

说明:

1、如果两个相同长度的字符串s和t,s中相同的字母能由t中相同位置上的同一个字母来代替,那么它是同构的。比如“add”和“egg”,a由相同位置上的e代替,d由相同位置上的g代替。也就是说要建立对应关系。

2、不能两个不同的字母对应同一个字母,比如“ab”和“ee”就不是同型的,“ee”和“ab”也不是同型的。

3、但是“paper”和“title”是同型的,因为可以e对应l,r对应e。

根据上述规则,我们利用map可以构建出如下代码,一旦出现两个不同的字母试图对应同一个字母,就可以判断它是不同型的。

bool isIsomorphic(string s, string t) 
{
    map<char,char>m1;
    map<char,char>m2;
    for(int i=0;i<s.size();i++)//去除"foo"和“bar”这种同一个字母对应两个的情况
    {
        if(!m1[s[i]])
        m1[s[i]]=t[i];
        else
        {
            if(m1[s[i]]!=t[i])
            return false;
        }
    }
    for(int i=0;i<t.size();i++)//去除“ab”和“ee”这种两个字母对应同一个的情况
    {
        if(!m2[t[i]])
        m2[t[i]]=s[i];
        else
        {
            if(m2[t[i]]!=s[i])
            return false;
        }
    }
    return true;
}

上述代码实测12ms,beats 51.61% 0f cpp submissions。

4、改进

在discuss区看到了这样的代码,也不难理解。

bool isIsomorphic(string s, string t) 
{
        char map_s[128] = { 0 };
        char map_t[128] = { 0 };
        int len = s.size();
        for (int i = 0; i < len; ++i)
        {
            if (map_s[s[i]]!=map_t[t[i]]) return false;
            map_s[s[i]] = i+1;
            map_t[t[i]] = i+1;
        }
        return true;    
}

实测9ms,beats 71.54% of cpp submissions。

还有一大堆人做出来7ms的方法,很好奇……

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Flutter入门

Android OpenGL ES(一)-开始描绘一个平面三角形

今天的目标是做一个OpenGL ES学习的开端。就是画一个简单的三角形。暂时不考虑坐标系的矩阵变换和纹理等。只需要用顶点着色器简单的来进行描述。 这一节需要使...

2382
来自专栏刘望舒

kotlin到底好在哪里?

最近在学kotlin,虽然还没有像其他博主一样立马就爱上它.但是不得不说,kotlin对比起java还是有不少优势的. 1、语法简洁 首先是语法比较简洁,能不简...

3577
来自专栏诸葛青云的专栏

C语言位运算的妙用你知道多少?

位运算在驱动开发中是经常遇到的,尤其是置0和置1。既要指定的位数发生变化,又不能改变其它位的值,还要高效率的编写代码,这时候技巧就很重要了。在位运算中有几个符号...

2004
来自专栏算法修养

ZOJ 1648 Circuit Board(计算几何)

Circuit Board Time Limit: 2 Seconds Memory Limit: 65536 KB On the circu...

2083
来自专栏云瓣

JS家的排序算法

由于浏览器的原生支持(无需安装任何插件),用JS来学习数据结构和算法也许比c更加便捷些。因为只需一个浏览器就能啪啪啪的调试了。比如下图我学习归并排序算法时,只看...

4268
来自专栏desperate633

LeetCode 350. Intersection of Two Arrays II题目分析代码

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

1166
来自专栏微信公众号:Java团长

Java泛型详解

Java泛型是jdk1.5中引入的一个新特性,泛型提供了编译时的类型检测机制,该机制允许程序员在编译时检测到非法的类型。 泛型是Java中一个非常重要的知识点,...

1171
来自专栏余林丰

Effective Java通俗理解(上)

  这篇博客是Java经典书籍《Effective Java(第二版)》的读书笔记,此书共有78条关于编写高质量Java代码的建议,我会试着逐一对其进行更为通俗...

2907
来自专栏Coding+

JS 中的一些概念问题

在 JS 中,每个对象都会在内部引用一个叫做prototype的对象,而这个原型对象本身也会引用自己的原型对象,并以此类推。这样就形成了一条原型引用链,这个链的...

1023
来自专栏数据结构与算法

610. 数对的个数

★★   输入文件:dec.in   输出文件:dec.out 简单对比 时间限制:1 s   内存限制:128 MB Description 出题是一件...

2927

扫码关注云+社区

领取腾讯云代金券