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/
- 题目内容：
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。
两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例 1:
输入: s = "egg", t = "add"
输出: true
示例 2:
输入: s = "foo", t = "bar"
输出: false
示例 3:
输入: s = "paper", t = "title"
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。
小伙伴可以先自己在本地尝试解题，再回来看看 jsliang 的解题思路。
- 解题代码：
var isIsomorphic = function(s, t) {
let sMap = new Map(); // 记录 s 哈希表
let tMap = new Map(); // 记录 t 哈希表
let sFlag = 0;
let tFlag = 0;
for (let i = 0; i < s.length; i++) {
if (sMap.get(s[i])) {
s[i] = sMap.get(s[i]);
} else {
sFlag++;
sMap.set(s[i], sFlag);
s[i] = sFlag;
}
if (tMap.get(t[i])) {
t[i] = tMap.get(t[i]);
} else {
tFlag++;
tMap.set(t[i], tFlag);
t[i] = tFlag;
}
if (sMap.get(s[i]) !== tMap.get(t[i])) {
return false;
}
}
return true;
};- 执行测试：
s：abt：acreturn：true
- LeetCode Submit：
✔ Accepted
✔ 30/30 cases passed (116 ms)
✔ Your runtime beats 44.62 % of javascript submissions
✔ Your memory usage beats 17.35 % of javascript submissions (39.8 MB)- 知识点：
map()：遍历数组，item返回遍历项，index返回当前索引。map()详细介绍
- 解题思路：
最愚蠢的就是老想着奇技淫巧。
首先，我们分两个 Map() 记录哈希表（如果只有一个 Map()，碰到 ab 和 ac 这种组合的时候会挂），使用 sFlag 和 tFlag 来表示这个字符是否重复出现。
然后，我们判断 s 的 Map() 和 t 的 Map() 是否有已经出现的字符串，如果出现，则直接设置值；如果没出现，则先设置下 Map() 值，再设置下这个位置的值。
最后，判断这两个值是否相同，相同则是 true，否则是 false。
- 解题代码：
var isIsomorphic = function(s, t) {
for (let i = 0; i < s.length; i++) {
if (s.indexOf(s[i]) !== t.indexOf(t[i])) {
return false;
}
}
return true;
};- 执行测试：
s：abt：acreturn：true
- LeetCode Submit：
✔ Accepted
✔ 30/30 cases passed (84 ms)
✔ Your runtime beats 93.08 % of javascript submissions
✔ Your memory usage beats 92.86 % of javascript submissions (35 MB)- 知识点：
indexOf()：判断数组中是否存在判断条件中的值。如果存在，则返回第一次出现的索引；如果不存在，则返回 -1。indexOf()详细介绍
- 解题思路：
人比人，气死人。
大佬思想：因为 indexOf 会返回遍历这个字符串的遇到一个第一个指定值的下标，所以判断两个下标是否一样即可。
不折腾的前端，和咸鱼有什么区别！
jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。
扫描上方二维码，关注 jsliang 的公众号，让我们一起折腾！
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。
