1170. Compare Strings by Frequency of the Smallest Character

Let the function f(s) be the frequency of the lexicographically smallest character in a non-empty string s. For example, if s = "dcce" then f(s) = 2 because the lexicographically smallest character is 'c', which has a frequency of 2.

You are given an array of strings words and another array of query strings queries. For each query queries[i], count the number of words in words such that f(queries[i]) < f(W) for each W in words.

Return  an integer array answer , where each  answer[i]  is the answer to the  ith  query.

Example 1:

Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

Example 2:

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

Constraints:

  • 1 <= queries.length <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].length, words[i].length <= 10
  • queries[i][j]words[i][j] consist of lowercase English letters.

这道题定义了一个函数f,是求字符串中字母顺序最小的字符出现的次数,现在给了个单词数组 words,和一个查询数组 queries,让对于每个 queries 数组中的单词,找出 words 数组中所有f值大于查询单词f值的个数。对于一道 Medium 的题来说,应该不会有太多的技巧在里面,首先肯定是要先找出每个单词的f值,这可以放到一个子函数中来处理,处理方法也很直接,給字符排序,然后遍历字符串,遇到和首字符不同的位置时,返回当前位置的坐标即可,循环退出后返回整个字符串的长度。对 words 数组中的每个单词都计算出了f值之后,为了查找方便,博主的做法是給其排序,这样可以用二分搜索法快速的定位出定一个大于目标值的位置,然后就知道有多少个大于目标值的数字了。遍历 queries 数组的每一个单词 query,计算其f值,然后在 freq 数组用 upper_bound 来查找第一个大于查询单词的f值的位置,然后用末尾位置减去查询位置就是个数了,参见代码如下:

解法一:

class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> res, freq;
        for (string word : words) {
            freq.push_back(f(word));
        }
        sort(freq.begin(), freq.end());
        for (string query : queries) {
            int cnt = f(query);
            auto it = upper_bound(begin(freq), end(freq), cnt);
            res.push_back(freq.end() - it);
        }
        return res;
    }
    
    int f(string s) {
        sort(s.begin(), s.end());
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != s[0]) return i;
        }
        return s.size();
    }
};

我们可以进一步的优化时间复杂度,由于这里的单词长度不超过 10 个,所以频率也就不超过 10,这样就用一个频率数组 freq,其中 freq[i] 表示 words 数组中单词的f值为i的个数,开始时遍历 words 数组,计算每个单词的f值并更新 freq 数组。然后为了查找所有大于某个频率的数字方便,需要建立累加数组,这里是反向的累加数组,更新后的 freq[i] 表示原数组 [i, end] 范围内的数字之和。建立好反向数组之后,遍历 queries 数组,计算每个 query 单词的f值,然后在 freq 数组中查找该f值加1的位置的值加入结果 res 中即可,参见代码如下:

解法二:

class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> res, freq(12);
        for (string word : words) {
            ++freq[f(word)];
        }
        for (int i = 9; i >= 0; --i) {
            freq[i] += freq[i + 1];
        }
        for (string query : queries) {
            int cnt = f(query);
            res.push_back(freq[cnt + 1]);
        }
        return res;
    }
    
    int f(string s) {
        sort(s.begin(), s.end());
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != s[0]) return i;
        }
        return s.size();
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1170

参考资料:

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/discuss/366698/C%2B%2B-Keep-track-of-count-of-frequencies-Beats-100

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation