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

标签: 数组 哈希表 字符串 二分查找 排序

难度: Medium

定义一个函数 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] 都由小写英文字母组成

Submission

运行时间: 36 ms

内存: 16.5 MB

class Solution:
    def f(self, s: str) -> int:
        cnt = 0
        ch = 'z'
        for c in s:
            if c < ch:
                ch = c
                cnt = 1
            elif c == ch:
                cnt += 1
        return cnt

    def numSmallerByFrequency(self, queries: list[str], words: list[str]) -> list[int]:
        count = [0] * 12
        for s in words:
            count[self.f(s)] += 1
        for i in range(9, 0, -1):
            count[i] += count[i + 1]
        res = []
        for s in queries:
            res.append(count[self.f(s) + 1])
        return res

Explain

此题解采用了前缀和的思想。首先，定义一个辅助函数 f(s)，用于计算字符串 s 中按字典序最小的字母出现的次数。然后，对于词汇表 words 中的每个单词，计算其 f 值，并将对应的计数值加 1，存储在一个长度为 12 的数组 count 中，因为单词的最大长度为 10，所以 f 值的范围是 1 到 10。接着，从后往前对 count 数组进行累加，使得 count[i] 表示 f 值大于等于 i 的单词数量。最后，对于每个查询，通过查询 count 数组得到满足条件的单词数量。

时间复杂度: O(nL + m)

空间复杂度: O(m)

class Solution:
    def f(self, s: str) -> int:
        cnt = 0
        ch = 'z'
        for c in s:
            if c < ch:
                ch = c
                cnt = 1
            elif c == ch:
                cnt += 1
        return cnt

    def numSmallerByFrequency(self, queries: list[str], words: list[str]) -> list[int]:
        count = [0] * 12  # 初始化计数数组
        for s in words:
            count[self.f(s)] += 1  # 计算每个单词的 f 值并更新计数数组
        for i in range(9, 0, -1):
            count[i] += count[i + 1]  # 累加计数数组以得到前缀和
        res = []
        for s in queries:
            res.append(count[self.f(s) + 1])  # 查询满足条件的单词数量
        return res

Explore

在处理count数组时，选择从后向前累加是为了计算前缀和，具体地，这样可以使count[i]表示所有f值大于等于i的单词数量。如果从前向后累加，我们将得到后缀和，这不符合题目需要查询的条件，即查询所有f值大于某个特定值的单词数量。从后向前累加可以直接在查询时通过count[f(s) + 1]得到满足条件的单词数量，这样更直接有效。

在函数f中，选择'z'作为初始的ch变量是因为'z'是英文字母表中字典序最大的字母。这样做的目的是为了在遍历字符串s的过程中，任何一个字母都不会比'z'大，从而确保能够正确地找到最小的字母。理论上，任何大于或等于's'中最小字母的字符都可以作为初始值，但使用'z'是一个保守而安全的选择，因为它简化了逻辑且总是可行的。

count数组长度设为12而非11是为了方便处理边界情况，具体地，在计算查询结果时，我们需要访问count[f(s) + 1]。如果f(s)的最大值为10，那么f(s) + 1的最大值为11。如果数组长度只有11，那么访问count[11]将会越界。因此，将数组长度设为12可以避免这种越界错误，确保代码的安全和正确执行。

在实际编码中，确保每个单词的长度不超过10通常需要在输入处理阶段进行检查。这是因为如果输入数据不符合预期的约束，可能会导致程序错误或异常行为。进行长度检查可以增加程序的健壮性，防止因输入不符导致的问题。在函数或方法的开始部分添加检查逻辑，如果发现任何单词长度超过10，可以抛出异常或返回错误信息，从而确保后续逻辑处理的正确性和稳定性。