我们来定义一个函数?f(s)，其中传入参数?s?是一个非空字符串；
该函数的功能是统计?s ?中（按字典序比较）最小字母的出现频次。
例如，若?s = "dcce"，那么?f(s) = 2，因为最小的字母是?"c"，它出现了?2 次。
现在，给你两个字符串数组待查表?queries?和词汇表?words，
请你返回一个整数数组?answer?作为答案
其中每个?answer[i]?是满足?f(queries[i])?< f(W)?的词的数目，W?是词汇表?words?中的词。
示例 1：
输入：queries = ["cbd"], words = ["zaaaz"]
输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
示例 2：
输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/compare-strings-by-frequency-of-the-smallest-character/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
渐进题解 1
1、循环 `待查表` ，计算 `待查表` 当前元素的 `最小字符出现频次`
2、在外循环中，循环 `词汇表`
将 `待查表` 与 `词汇表` 的 `最小字符频次` 比较
3、满足条件，`count` 加 1
4、记录 `count`
渐进题解 1
1、预先计算 `词汇表` 中每个词汇的 `最小字符出现频次` ，并存储，防止计算浪费
2、循环 `待查表` ，并计算 `最小字符频次`
循环上面得到的 `词汇表最小字符出现频次数组` ，与当前 `待查表最小字符频次` 进行对比
3、满足条件 `count` 加 1
4、记录 `count`
力扣较好题解
1、循环 `词汇表` ，计算每个词汇的 `最小字符出现频次`
将该频次作为 `counter` 数组下标，并且数组下标对应的元素数值加 1
例如表示 `最小字符出现频次` 为 5 的词汇增加一个（有继续出现频次为 5 的，那么计数继续加 1）
2、在计数数组 `counter` 中，倒序对 `相邻两位` 进行叠加
即可得到 `counter` 中，大于等于当前 `最小字符出现频次` 的词汇有多少个
3、循环 `待查表` ，计算得到当前 `待查表字符串` 中的 `最小字符出现频次`
要满足 `待查表的频次 < 词汇表的频次`
那么可以反过来理解为： `词汇表中频次 > 待查表的频次` 的词汇有多少个
即在计数数组中，`待查表的频次 + 1` 的数组下标对应的值，就是满足条件的词汇个数
渐进题解 1
// 用时很长，内存消耗也大
执行用时: 7904 ms
内存消耗: 42.7 MB
let numSmallerByFrequency = function(queries, words) {
let ans = []
// 循环待查表
queries.forEach(query => {
let count = 0
// 计算待查表当前元素的最小字母出现频次
let qc = calcMinCount(query)
// 循环词汇表
words.forEach(word => {
// 将待查表与词汇表的最小字母频次比较
if (qc <= word.length && qc < calcMinCount(word)) {
// 满足条件，次数加 1
count++
}
})
// 记录 count
ans.push(count)
})
return ans
}
/**
* 计算字符串中最小字母的出现频次
*/
function calcMinCount (string) {
// 切割字符串，并排序，第一个字符就是最小字符。
// 正则匹配得到该字符出现的次数
return string.match(new RegExp(string.split(‘‘).sort()[0], ‘g‘)).length
}
渐进题解 2
// 用时一般，内存消耗一般
执行用时: 116 ms
内存消耗: 39.7 MB
let numSmallerByFrequency = function(queries, words) {
let wCount = [], ans = []
// 预先计算词汇表中每个词汇的最小字符出现频次，并存储，防止计算浪费
words.forEach(word => {
wCount.push(calcMinCount(word))
})
// 循环待查表
queries.forEach(query => {
let count = 0
let qc = calcMinCount(query)
// 循环词汇表最小字符出现频次数组，进行对比
wCount.forEach(w => {
if (qc < w) {
// 满足条件 count 加 1
count++
}
})
// 记录 count
ans.push(count)
})
return ans
}
/**
* 计算字符串中最小字母的出现频次
*/
function calcMinCount (string) {
let l = ‘abcdefghijklmnopqrstuvwxyz‘
// 循环已排序的 26 个字母
for (const s of l) {
// 若在字符串中能找到当前字符，说明当前字符即是这个字符串中的最小字符
if (string.indexOf(s) > -1) {
// 正则匹配得到最小字符的个数
return string.match(new RegExp(s, ‘g‘)).length
}
}
}
力扣较好题解
// 用时较好，内存消耗较好
执行用时: 88 ms
内存消耗: 37.5 MB
let numSmallerByFrequency = function(queries, words) {
const res = []
// 题目有约束 queries[i]、words[i] 的最大长度为 10
// 意味着，最小字符出现频次最大为 10
// 因为下面需要使用数组下标来表示 最小字符出现频次，并且会进行相邻元素进行叠加操作
// 所以这里本因创建一个长度为 11（因为数组下标为10），值都为 0 的数组
// 但是在最后的比较处理上，需要多一位，所以实际要创建长度为 12 的数组
let counter = Array.from({ length: 12 }, () => 0)
// 循环词汇表，计算每个词汇的最小字符出现频次
// 将该频次作为 counter 数组下标，并且数组下标对应的元素数值加 1
// 表示最小字符出现频次为 5 的词汇增加一个（有继续出现频次为 5 的，那么计数继续加 1）
// 例如： counter:>> [ 0, 1, 1, 1,1, 0, 0, 0, 0, 0, 0, 0 ]
// 表示词汇表中最小字符出现频次为 1、2、3、4 次数(数组下标)的词汇，各出现一次
for (let i = 0; i < words.length; i++)
counter[calcMinCount(words[i])]++
console.log(‘counter :>> ‘, counter);
// 在计数数组 counter 中，倒序对相邻两位进行叠加
// 即可得到 counter 中，大于等于当前最小字符出现频次的词汇有多少个
// 例如
// 叠加前: counter :>> [ 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 ]
// 叠加后: counter :>> [ 4, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0 ]
// 叠加后，意为最小字符出现频次为:
// 0 且之后的词汇有 4 个
// 1 且之后的词汇有 4 个
// 2 且之后的词汇有 3 个
// 3 且之后的词汇有 2 个
// 4 且之后的词汇有 1 个
// ...
for (let i = 10; i >= 0; i--)
counter[i] += counter[i+1]
// 循环待查表，计算得到当前待查表字符串中的最小字符出现频次
// 要满足 待查表的频次 < 词汇表的频次
// 那么可以反过来理解为： 词汇表中频次 大于 待查表的频次 的词汇有多少个
// 即在计数数组中，待查表的频次 + 1 的数组下标对应的值，就是满足条件的词汇个数
for (let i = 0; i < queries.length; i++)
res.push(counter[calcMinCount(queries[i]) + 1])
return res
}
/**
* 计算字符串中最小字母的出现频次
*/
const calcMinCount = string => {
if (string.length < 2)
return 1
let s = string[0],
max = 1
// 循环字符串
for (let i = 1; i < string.length; i++) {
const _s = string[i]
// 若当前字符小于对比字符
// 则将对比字符赋值了当前字符，并且最小字符出现频次重置为 1
if (_s < s) {
s = _s
max = 1
} else if (_s === s) {
// 若等于，则最小字符出现频次加 1
max++
}
}
return max
}
LeetCode --- 字符串系列 --- 比较字符串最小字母出现频次
原文：https://www.cnblogs.com/linjunfu/p/12776193.html