JS leetcode 宝石与石头 题解分析,正则字符组也有妙用

天高任鸟飞 2020-06-13

壹 ? 引

简单问题简单做,今天的题目来自leetcode771. 宝石与石头,字符串相关的一道题,题目描述如下:

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,JS中的所有字符都是字母。字母区分大小写,因此"a""a"是不同类型的石头。

示例 1:

输入: J = "aA", S = "aAAbbbb"
输出: 3

示例 2:

输入: J = "z", S = "ZZ"
输出: 0

注意:

  • SJ 最多含有50个字母。
  • J 中的字符不重复。

我们先来简单的分析问题,因为题目简单,我们尽可能灵活运用掌握的知识,多一些可能去实现它。

贰 ? 解题思路

我们来汇总题目信息,首先S表示宝石,S中的每种字符都是一种宝石类型,且S不存在重复,也就是每个字符只会出现一次。

J的每个字符都是一种石头,且区分大小写,也会重复,我们要做的,就是要看手上的石头中,一共有多少课是宝石。综上来说,也就是要看S中的每个字符出现在J中的次数统计。

那么我们首先能想到的就是最暴力的解法,使用双层遍历,S表现一共要查多少遍,J表示每遍要查多少次,直接上代码:

/**
 * @param {string} J
 * @param {string} S
 * @return {number}
 */
var numJewelsInStones = function (J, S) {
    let j_len = J.length,
        s_len = S.length,
        ans = 0;// 统计宝石个数
    for (let i = 0; i < j_len; i++) {
        for (let k = 0; k < s_len; k++) {
            if (J[i] === S[k]) {
                ans++;
            }
        };
    };
    return ans.length;
};

当到这时,我突然意识到一个问题,由于题目已经说了S中宝石不存在重复,也就是说只要一颗宝石出现过,后面就不会再出现,那对于J而言,已经查出的宝石是没必要再参与下次查找的。

这样针对J特别大的情况,随着宝石查询次数增多,J中的剩余石头会越来越少,自然越查越快,于是我有了如下思路:

/**
 * @param {string} J
 * @param {string} S
 * @return {number}
 */
var numJewelsInStones = function (J, S) {
    var j_len = J.length,
        S = S.split(""),// 这里将宝石转成数组,便于每次查询后清除掉已查到的宝石
        ans = "";
    for (let i = 0; i < j_len; i++) {
        for (let k = 0; k < S.length;) {
            if (J[i] === S[k]) {
                ans += S[k];
                //将已找到的宝石清除掉
                S.splice(k, 1);
            } else {
                k++;
            };
        };
    };
    return ans.length;
};

通过这样修改,相比上次效率就快了不少,非常棒。

有没有其它做法,让我们想想,我们要在S中找有没有J包含的字符,以及找出遍布在S中所有满足J的字符,这样一想,J不就是正则匹配条件吗。我们知道正则有字符组的概念,举个例子:

let reg = /[aA]/g

这段正则表示匹配所有的小写a与大写A,如下图:

JS leetcode 宝石与石头 题解分析,正则字符组也有妙用

所以不管J有几个字符,我们只用/[J]/即可,所以可以这样:

/**
 * @param {string} J
 * @param {string} S
 * @return {number}
 */
var numJewelsInStones = function (J, S) {
    // 考虑到可能匹配不到,所以得用三元判断一次
	let ans = S.match(new RegExp(‘[‘ + J + ‘]‘, ‘g‘));
  	return ans ? ans.length : 0
};

你看,活用正则也能解决这个问题。

其实之前我发现对比直接遍历字符,如果转成数组遍历似乎会快一些,我当时以为是leetcode提供的例子差异问题,但这次似乎又加深了我这种感觉,我们将S与J都转成数组进行遍历:

/**
 * @param {string} J
 * @param {string} S
 * @return {number}
 */
var numJewelsInStones = function (J, S) {
  let j = J.split("");
  let s = S.split("");
  // 将j包含的元素全部过滤到新数组中,并返回长度
  return s.filter(item => j.includes(item)).length;
};

这里主要借用了includes方法,它用来判断数组是否包含某个元素,并返回布尔值。我们都知道NaN不等于自己,在判断是否包含NaN就很麻烦,而这个API恰好就能解决这个问题,比如:

[1,NaN,1].includes(NaN);// true
[1,1].includes(NaN);// false

题目虽然简单,但我们还是尽力拓展思维,复习了一些有趣的API以及正则小知识,那么关于本题就说到这了。

相关推荐