242 - 有效的字母异位词(valid-anagram)

Create by jsliang on 2019-07-17 18:53:04
Recently revised in 2019-07-17 19:22:29

一 目录

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

目录
一 目录
二 前言
三 解题
3.1 解法 - 暴力破解
3.2 解法 - Map

二 前言

返回目录

示例 1:
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

三 解题

返回目录

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

3.1 解法 - 暴力破解

返回目录

  • 解题代码
var isAnagram = function(s, t) {
  return s.split('').sort().join('') === t.split('').sort().join('');
};
  • 执行测试

  • sanagram

  • tnagaram
  • returntrue

  • LeetCode Submit

✔ Accepted
  ✔ 34/34 cases passed (168 ms)
  ✔ Your runtime beats 42.71 % of javascript submissions
  ✔ Your memory usage beats 42.44 % of javascript submissions (38.1 MB)
  • 知识点

  • split()split() 方法使用指定的分隔符字符串将一个 String 对象分割成字符串数组,以将字符串分隔为子字符串,以确定每个拆分的位置。split() 详细介绍

  • sort():排序,保持返回数组的数字、字母为顺序排列。sort() 详细介绍
  • join()join() 方法将一个数组(或一个类数组对象)的所有元素连接成一个字符串并返回这个字符串。join() 详细介绍

  • 解题思路

毫无技巧的碾压,是暴力破解的快乐

首先,什么是异位词?

假设字符串 sabcdtcdad,那么它两就是异位。

即:字母出现的次数相等的两个词,就是异位词。

然后,我们就可以方便破解了:将它们打成数组,排序,再打成字符串。如果相同,即是异位词。

最后,希望小伙伴们不要被题意迷惑,其实有时候往往解题很简单。

3.2 解法 - Map

返回目录

  • 解题代码
var isAnagram = function(s, t) {
  if (s.length !== t.length) {
    return false;
  }
  let map = new Map();
  for (let i = 0; i < s.length; i++) {
    if (map.get(s[i])) {
      map.set(s[i], map.get(s[i]) + 1);
    } else {
      map.set(s[i], 1);
    }
  }
  for (let j = 0; j < t.length; j++) {
    if (map.get(t[j])) {
      map.set(t[j], map.get(t[j]) - 1);
      if (map.get(t[j]) === 0) {
        map.delete(t[j]);
      }
    }
  }
  return !map.size;
};
  • 执行测试

  • sanagram

  • tnagaram
  • returntrue

  • LeetCode Submit

✔ Accepted
  ✔ 34/34 cases passed (116 ms)
  ✔ Your runtime beats 72.3 % of javascript submissions
  ✔ Your memory usage beats 74.35 % of javascript submissions (36.2 MB)
  • 知识点

  • Map:保存键值对。任何值(对象或者原始值) 都可以作为一个键或一个值。Map 详细介绍

  • 解题思路

首先,判断两个字符串的长度是否一致,如果不是,那么这两者肯定不是异位词。

然后,执行两次遍历:

  1. 遍历第一次,记录每个单词出现的次数。
  2. 遍历第二次,记录这个单词是否出现过,如果出现了,则消除对应的次数。如果对应的次数为 0,则消除这个元素(表明这个元素没有问题了)。

最后,判断 Map 是否还有值,一般来说,StringArray 通过 length 属性来判断,而 Map 通过 size 来判断。

在这里,jsliang 通过两种解法破解了这道题,小伙伴们有没有更加优秀的题解?欢迎留言或者评论~


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

图

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

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

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

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-17 19:22:29

results matching ""

    No results matching ""