橙子何橙

V1

2022/11/08阅读:39主题:萌绿

学算法刷LeetCode:1684. 统计一致字符串的数目

Problem: 1684. 统计一致字符串的数目

思路

这道题其实就是在 words 里面的每个字符串找是否有不在 allowed 中的字母出现。

解题方法

我们可以把 allowed 中的字母放到哈希表中,需要查询的时候直接取出来即可。我们只需要遍历 words 以及 words[i] 中字母,每个字母都去哈希表中查询一下是不是包含不存在的字母,如果有,则说明这个结果不符合,不统计总结果的数量中,反之,总结果累加。

复杂度

  • 时间复杂度:

,其中 mwords[i] 的长度。

  • 空间复杂度:

Code


/**
 * @param {string} allowed
 * @param {string[]} words
 * @return {number}
 */

var countConsistentStrings = function(allowed, words{
    const map = new Map();
    for (let i = 0; i < allowed.length; i++) {
        map.set(allowed[i], (map.get(allowed[i]) || 0) + 1);
    }

    let res = 0;
    for(let ch of words) {
        let flag = false;
        for(let i = 0; i < ch.length; i++) {
            if(!map.has(ch[i])){
                flag = true;
                break;
            }
        }
        if(!flag) res++;
    }
    return res;
};

分类:

前端

标签:

数据结构与算法

作者介绍

橙子何橙
V1

前端工程师