[LeetCode] 1170. Compare Strings by Frequency of the Smallest Character

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)