LeetCode - 205 - 同构字符串(isomorphic-strings)

栏目: IT技术 · 发布时间: 4年前

内容简介:LeetCode - 205 - 同构字符串(isomorphic-strings)

Create by jsliang on 2019-07-12 18:40:54
Recently revised in 2019-07-12 19:29:09

一 目录

不折腾的前端,和咸鱼有什么区别

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | |  3.1 解法 - Map() | |  3.2 解法 - indexOf() |

二 前言

  • 难度:简单

  • 涉及知识:哈希表

  • 题目地址:https://leetcode-cn.com/problems/isomorphic-strings/

  • 题目内容

  1. 给定两个字符串 s  t,判断它们是否是同构的。

  2. 如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。

  3. 所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。

  4. 两个字符不能映射到同一个字符上,但字符可以映射自己本身。

  5. 示例 1:

  6. 输入: s = "egg", t = "add"

  7. 输出: true

  8. 示例 2:

  9. 输入: s = "foo", t = "bar"

  10. 输出: false

  11. 示例 3:

  12. 输入: s = "paper", t = "title"

  13. 输出: true

  14. 说明:

  15. 你可以假设 s  t 具有相同的长度。

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - Map()

  • 解题代码

  1. var isIsomorphic = function(s, t) {

  2. let sMap = new Map(); // 记录 s 哈希表

  3. let tMap = new Map(); // 记录 t 哈希表

  4. let sFlag = 0;

  5. let tFlag = 0;

  6. for (let i = 0; i < s.length; i++) {

  7. if (sMap.get(s[i])) {

  8. s[i] = sMap.get(s[i]);

  9. } else {

  10. sFlag++;

  11. sMap.set(s[i], sFlag);

  12. s[i] = sFlag;

  13. }

  14. if (tMap.get(t[i])) {

  15. t[i] = tMap.get(t[i]);

  16. } else {

  17. tFlag++;

  18. tMap.set(t[i], tFlag);

  19. t[i] = tFlag;

  20. }

  21. if (sMap.get(s[i]) !== tMap.get(t[i])) {

  22. return false;

  23. }

  24. }

  25. return true;

  26. };

  • 执行测试

  1. s: ab

  2. t: ac

  3. return: true

  • LeetCode Submit

  1. Accepted

  2. 30/30 cases passed (116 ms)

  3. Your runtime beats 44.62 % of javascript submissions

  4. Your memory usage beats 17.35 % of javascript submissions (39.8 MB)

  • 知识点

  1. map():遍历数组, item 返回遍历项, index 返回当前索引。 map() 详细介绍

  • 解题思路

最愚蠢的就是老想着奇技淫巧

首先,我们分两个 Map() 记录哈希表(如果只有一个 Map(),碰到 abac 这种组合的时候会挂),使用 sFlagtFlag 来表示这个字符是否重复出现。

然后,我们判断 sMap()tMap() 是否有已经出现的字符串,如果出现,则直接设置值;如果没出现,则先设置下 Map() 值,再设置下这个位置的值。

最后,判断这两个值是否相同,相同则是 true,否则是 false

3.2 解法 - indexOf()

  • 解题代码

  1. var isIsomorphic = function(s, t) {

  2. for (let i = 0; i < s.length; i++) {

  3. if (s.indexOf(s[i]) !== t.indexOf(t[i])) {

  4. return false;

  5. }

  6. }

  7. return true;

  8. };

  • 执行测试

  1. s: ab

  2. t: ac

  3. return: true

  • LeetCode Submit

  1. Accepted

  2. 30/30 cases passed (84 ms)

  3. Your runtime beats 93.08 % of javascript submissions

  4. Your memory usage beats 92.86 % of javascript submissions (35 MB)

  • 知识点

  1. indexOf():判断数组中是否存在判断条件中的值。如果存在,则返回第一次出现的索引;如果不存在,则返回 -1。 indexOf() 详细介绍

  • 解题思路

人比人,气死人

大佬思想:因为 indexOf 会返回遍历这个字符串的遇到一个第一个指定值的下标,所以判断两个下标是否一样即可。


不折腾的前端,和咸鱼有什么区别!

LeetCode - 205 - 同构字符串(isomorphic-strings)

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

LeetCode - 205 - 同构字符串(isomorphic-strings)

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。



以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Big C++中文版

Big C++中文版

霍斯特曼 / 姚爱红 / 电子工业 / 2007-3 / 85.00元

本书是一本关于C++的优秀教材,南圣何塞州立大学知名教授Horstmann编写。全书深入探讨了C++的知识,并着重强调了安全的标准模板库;本书较厚,但它可用做程序设计专业学生的教材(两学期)。全书在介绍基础知识后,作者论及了一些高级主题。书中面向对象的设计一章探讨了软件开发生命周期问题,给出了实现类关联的实用提示。其他高级主题包括模板,C++标准模板库,设计模式,GUI,关系数据库以及XML等。本......一起来看看 《Big C++中文版》 这本书的介绍吧!

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具