1170. 比较字符串最小字母出现频次

题目

TIP

我们来定义一个函数 f(s)，其中传入参数 s 是一个非空字符串；该函数的功能是统计 s  中（按字典序比较）最小字母的出现频次。

例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。

现在，给你两个字符串数组待查表 queries 和词汇表words，请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。

示例

输入：queries = ["cbd"], words = ["zaaaz"]
输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。

输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。

解答

• 自己的答案，超出时间限制，部分案例可以通过

/**
 * @param {string[]} queries
 * @param {string[]} words
 * @return {number[]}
 */
var numSmallerByFrequency = function(queries, words) {
    let sortStr = function(str) {
        let arr = str.split('').sort()
        let total = 1
        for(let i =1;i<arr.length;i++) {
            if(arr[i] === arr[0]) {
                total +=1
            } else {
                break;
            }
        }
        return total
    }
    let result = []
    for(let i=0;i<queries.length;i++) {
        let num=0
        for(let j = 0;j<words.length;j++) {
            if(sortStr(queries[i]) < sortStr(words[j])) {
                num++
            }
        }
        result.push(num)
    }
    return result
};

var numSmallerByFrequency = function(queries, words) {
    let getFrequency = (str) => {
        let arr = str.split('').sort().join('')
        let smallestStr = arr[0]
        let num = 1
        for(let i = 1; i < arr.length; i++) {
            if (arr[i] === smallestStr) {
                num++
            } else {
                break
            }
        }
        return num
    }
    let list = new Array(12).fill(0)
    let result = []
    for(let i of words) {
        list[getFrequency(i)]++
    }
    for(let i = 10; i >= 0; i--) {
        list[i] += list[i+1]
    }
    for(let i of queries) {
        result.push(list[getFrequency(i) + 1])
    }
    return result
};