【leetcode】有效的字母异位

ConardLi

发布于 2019-05-23 21:49:00

4330

发布于 2019-05-23 21:49:00

文章被收录于专栏：code秘密花园code秘密花园

本系列是《剑指offer》或leetcode的JavaScript版本。每期1-2个算法，也有可能是一个类别。文章包括题目、思路以及代码。

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例 1:

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

示例 2:

输入: s = "rat", t = "car"输出: false

说明:

你可以假设字符串只包含小写字母。

解法

解法1:

1.使用两个map存储两个字符串中每个字符出现的次数

2.比较两个map存储的值是否相等

   /**    * @param {string} s    * @param {string} t    * @return {boolean}    * 使用两个map存储    */    var isAnagram = function (s, t) {      let success = false;      if (s !== undefined && t !== undefined && s.length === t.length) {        const sMap = new Map();        const tMap = new Map();        for (let i = 0; i < s.length; i++) {          const is = s.charAt(i);          const it = t.charAt(i);          const sCount = sMap.get(is);          const tCount = tMap.get(it);          if (sCount) {            sMap.set(is, sCount + 1);          } else {            sMap.set(is, 1);          }          if (tCount) {            tMap.set(it, tCount + 1);          } else {            tMap.set(it, 1);          }        }        if (sMap.size === tMap.size) {          success = true;          sMap.forEach((value, key) => {            if (value != tMap.get(key)) {              success = false;              return false;            }          })        }      }      return success;    };

解法2:

使用数组做存储。

用两个数组存储，比map要快，相当于手动实现了hashtable。

借助字符的特点，使用字符ascii码做下标。

以后遇到要给字符计数的情况都可以这样存储。

newArray(26).fill(0):初始化一个长度为26的默认值为0的数组。

    var isAnagram = function (s, t) {      let success = false;      if (s !== undefined && t !== undefined && s.length === t.length) {        const start = 'a'.charCodeAt(0);        const sArr = new Array(26).fill(0);        const tArr = new Array(26).fill(0);        for (let i = 0; i < s.length; i++) {          sArr[s.charCodeAt(i) - start]++;          tArr[t.charCodeAt(i) - start]++;        }        success = sArr.toString() === tArr.toString();      }      return success;    };