跳转至

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

来源第 151 场周赛 Q2难度中等分数1431

题目描述

定义一个函数 f(s)，统计 s  中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。

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

现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。

请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。

 

示例 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")。

 

提示：

  • 1 <= queries.length <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].length, words[i].length <= 10
  • queries[i][j]、words[i][j] 都由小写英文字母组成

解法

方法一：排序 + 二分查找

思考

每个查询要数 \(words\) 中 \(f\) 值严格更大的个数。对每个查询扫描全部 \(words\) 为 \(O(qn)\)。先把每个 \(f(w)\) 算出并排序，查询时二分第一个大于 \(f(q)\) 的位置，右侧长度即为答案。\(f\) 只依赖最小字母的次数，对短串线性可求。

我们先按照题目描述，实现函数 \(f(s)\)，函数返回字符串 \(s\) 中按字典序比较最小字母的出现频次。

接下来，我们将 \(words\) 中的每个字符串 \(w\) 都计算出 \(f(w)\)，并将其排序，存放在数组 \(nums\) 中。

然后，我们遍历 \(queries\) 中的每个字符串 \(q\)，在 \(nums\) 中二分查找第一个大于 \(f(q)\) 的位置 \(i\)，则 \(nums\) 中下标 \(i\) 及其后面的元素都满足 \(f(q) < f(W)\)，那么当前查询的答案就是 \(n - i\)。

时间复杂度 \(O((n + q) \times M)\)，空间复杂度 \(O(n)\)。其中 \(n\) 和 \(q\) 分别是数组 \(words\) 和 \(queries\) 的长度，而 \(M\) 是字符串的最大长度。

1
2
3
4
5
6
7
8
9
class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        def f(s: str) -> int:
            cnt = Counter(s)
            return next(cnt[c] for c in ascii_lowercase if cnt[c])

        n = len(words)
        nums = sorted(f(w) for w in words)
        return [n - bisect_right(nums, f(q)) for q in queries]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int n = words.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = f(words[i]);
        }
        Arrays.sort(nums);
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int x = f(queries[i]);
            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (nums[mid] > x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            ans[i] = n - l;
        }
        return ans;
    }

    private int f(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        for (int x : cnt) {
            if (x > 0) {
                return x;
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        auto f = [](string s) {
            int cnt[26] = {0};
            for (char c : s) {
                cnt[c - 'a']++;
            }
            for (int x : cnt) {
                if (x) {
                    return x;
                }
            }
            return 0;
        };
        int n = words.size();
        int nums[n];
        for (int i = 0; i < n; i++) {
            nums[i] = f(words[i]);
        }
        sort(nums, nums + n);
        vector<int> ans;
        for (auto& q : queries) {
            int x = f(q);
            ans.push_back(n - (upper_bound(nums, nums + n, x) - nums));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func numSmallerByFrequency(queries []string, words []string) (ans []int) {
    f := func(s string) int {
        cnt := [26]int{}
        for _, c := range s {
            cnt[c-'a']++
        }
        for _, x := range cnt {
            if x > 0 {
                return x
            }
        }
        return 0
    }
    n := len(words)
    nums := make([]int, n)
    for i, w := range words {
        nums[i] = f(w)
    }
    sort.Ints(nums)
    for _, q := range queries {
        x := f(q)
        ans = append(ans, n-sort.SearchInts(nums, x+1))
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function numSmallerByFrequency(queries: string[], words: string[]): number[] {
    const f = (s: string): number => {
        const cnt = new Array(26).fill(0);
        for (const c of s) {
            cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        return cnt.find(x => x > 0);
    };
    const nums = words.map(f).sort((a, b) => a - b);
    const ans: number[] = [];
    for (const q of queries) {
        const x = f(q);
        let l = 0,
            r = nums.length;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (nums[mid] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        ans.push(nums.length - l);
    }
    return ans;
}

评论