[第32期] Set 和 Map 的简单运用
背景
#242 字母异位词，中午没事看到了这道题，easy 级别的一个题目， 就用了几种方法做了一下， 给大家伙看看。
题目描述：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
所谓字母异位词， 就是字母的组成一样， 只是位置不一样的单词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
正文
这个题目比较简单，属于一眼看过去就有思路的那种。
我用了三种解法，你也尝试一些别的方法， 拓宽思路。
- 暴力排序解法
- Set
- Map
Set 和 Map，这两种数据结构特别适合来做查询和计数, 在下面的代码中会有所体现。
解法1: 暴力排序
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
// 解法1: 暴力排序， NLogn
var isAnagram = function(s, t) {
return s.split('').sort().join('') === t.split('').sort().join('')
};第一种解法最容易想，也是最暴力的：字符串排序再比较。
这种方法，时间复杂度是O(NlogN)的。
如果面试的时候直接写这一种解法, 恐怕直接会被刷吧， 哈哈。
解法2: Set
这种方法也很简单。
直接统计字母的数量，遍历两个字符串集合的时候，一个用于加， 一个用于减.
如果之后集合里面的数字都是0， 说明两两抵消， 就是合法的字母异位词， 否则就不是。
因为 a 的 ASCII 对应的是97， b 的是98, 以此类推。
减掉97之后， 就是a 放在array[0]，b在array[1], 以此类推。
把对应的存入一个长度为26的集合里， 最后遍历一遍这个集合的数字是不是都为0即可。
这种方式的时间复杂度是O(N), 优于第一种方法。
代码实现，
// 方法2: Set
var isAnagram = function(s, t) {
if(s.length !== t.length) return false;
var ary = new Array(26).fill(0);
for(var i = 0; i < s.length; i++) {
ary[s[i].charCodeAt(0) - 97]++;
ary[t[i].charCodeAt(0) - 97]--;
}
for(var i = 0; i < ary.length; i++) {
if(ary[i] !== 0) return false;
}
return true
}解法3: Map
这种方法和第二种类似。只不过是用 map 代替了 array.
需要注意的是， 遍历之后， 得到的两个map, 需要比较是不是相同的，
Python 是可以直接比较的：
但是Javascript 不能直接比较， 需要简单实现一个deepEqual.
var deepEqual = function (x, y) {
// 指向同一内存时
if (x === y) {
return true;
} else if ((typeof x == "object" && x != null) && (typeof y == "object" && y != null)) {
if (Object.keys(x).length != Object.keys(y).length) return false;
for (var prop in x) {
if (y.hasOwnProperty(prop)) {
if (!deepEqual(x[prop], y[prop])) return false;
} else {
return false;
}
}
return true;
} else {
return false;
}
}再来比较就可以了。
简单的代码实现：
// 方法3: Map
var isAnagram = function(s, t) {
if(s.length !== t.length) return false;
var dic1 = {};
var dic2 = {}; for(var i = 0; i < s.length; i++) {
if( dic1[s[i]]) { // 出现过， 数量+1
dic1[s[i]]++;
} else { // 第一次出现， 数量为1
dic1[s[i]] = 1
}
}
for(var i = 0; i < t.length; i++) {
if( dic2[t[i]]) {
dic2[t[i]]++;
} else {
dic2[t[i]] = 1
}
}
return deepEqual(dic1, dic2)
}往期精彩回顾：