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

字符串算法探秘：最小字母频次统计与比较问题剖析

在编程的世界里，字符串处理问题犹如繁星般繁多且各具特色。今天，我们聚焦于一道饶有趣味的题目，它涉及到对字符串中最小字母出现频次的统计以及基于此的比较操作。这道题不仅考验我们对字符串基本操作的掌握程度，还能锻炼我们的算法思维和问题解决能力。

一、题目详述

1. 核心函数定义

首先，我们需要定义一个函数 f(s) ，它的任务是统计字符串 s 中按字典序比较最小字母的出现频次。这里的字典序就是我们平常所说的字母顺序，比如在英文字母表中，a 排在 b 前面，b 又排在 c 前面。例如，对于字符串 s = "dcce" ，我们先找到字典序最小的字母是 "c" ，然后统计它在字符串中出现的次数，发现出现了 2 次，所以 f(s) = 2 。

2. 数组比较任务

接着，题目给定了两个字符串数组，分别是待查表 queries 和词汇表 words 。我们的目标是对于 queries 数组中的每一个查询字符串 queries[i] ，统计 words 数组中满足 f(queries[i]) < f(W) 的词的数目，这里的 W 代表 words 数组中的每一个词。最后，要将每次查询的结果存储在一个整数数组 answer 中返回，其中 answer[i] 就是第 i 次查询的结果。

二、解题思路探索

1. 拆解 `f` 函数的实现

寻找最小字母：要实现 f 函数，我们首先要遍历字符串 s ，找到其中字典序最小的字母。可以通过一个简单的循环，从字符串的第一个字符开始，依次与后面的字符进行比较。如果遇到比当前最小字母还要小的字符，就更新最小字母。
统计最小字母频次：在找到最小字母后，再次遍历字符串 s ，统计这个最小字母出现的次数。通过这样两次遍历，就能准确计算出 f(s) 的值。

2. 整体流程规划

计算 queries 数组中每个字符串的 f 值：对于 queries 数组中的每一个字符串，调用 f 函数计算其最小字母的出现频次。
计算 words 数组中每个字符串的 f 值：同样，对 words 数组中的每一个字符串，也调用 f 函数计算其最小字母的出现频次。
比较与计数：对于 queries 数组中的每一个元素，遍历 words 数组，将 queries 元素的 f 值与 words 元素的 f 值进行比较。如果 queries 元素的 f 值小于 words 元素的 f 值，就将计数器加 1 。最后，将这个计数器的值存入 answer 数组中对应的位置。

三、代码实现展示（C 语言）

1. 实现 `f` 函数

// 计算字符串中字典序最小字母的出现频次
int f(char *s) {
    char minChar = s[0];
    for (int i = 1; i < strlen(s); i++) {
        if (s[i] < minChar) {
            minChar = s[i];
        }
    }
    int count = 0;
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == minChar) {
            count++;
        }
    }
    return count;
}

2. 主函数实现

// 统计满足条件的词汇表中词的数目
int* numSmallerByFrequency(char** queries, int queriesSize, char** words, int wordsSize, int* returnSize) {
    int* answer = (int*)malloc(queriesSize * sizeof(int));
    if (answer == NULL) {
        return NULL;
    }
    for (int i = 0; i < queriesSize; i++) {
        int queryFreq = f(queries[i]);
        int smallerCount = 0;
        for (int j = 0; j < wordsSize; j++) {
            int wordFreq = f(words[j]);
            if (queryFreq < wordFreq) {
                smallerCount++;
            }
        }
        answer[i] = smallerCount;
    }
    *returnSize = queriesSize;
    return answer;
}

3. 代码解释

f 函数：在 f 函数中，首先定义一个变量 minChar 并初始化为字符串 s 的第一个字符。然后通过一个 for 循环遍历字符串 s ，从第二个字符开始，每次比较当前字符与 minChar ，如果当前字符更小，就更新 minChar 。这样遍历完后，minChar 就是字符串中字典序最小的字母。接着，再通过另一个 for 循环遍历字符串 s ，统计 minChar 出现的次数，最后返回这个次数。
numSmallerByFrequency 函数：在这个主函数中，首先为 answer 数组分配内存空间，用于存储最终的查询结果。然后通过两层循环来实现查询和比较。外层循环遍历 queries 数组，对于每一个 queries[i] ，调用 f 函数计算其最小字母出现频次 queryFreq 。内层循环遍历 words 数组，对于每一个 words[j] ，调用 f 函数计算其最小字母出现频次 wordFreq 。如果 queryFreq 小于 wordFreq ，就将 smallerCount 加 1 。内层循环结束后，将 smallerCount 的值存入 answer[i] 。最后，设置 returnSize 为 queriesSize ，并返回 answer 数组。

四、复杂度分析

1. 时间复杂度

f 函数：f 函数需要遍历字符串两次，每次遍历的时间复杂度与字符串的长度成正比。假设字符串长度为 n ，那么 f 函数的时间复杂度为 $O(n)$ 。
整体算法：对于 queries 数组中的每一个字符串（假设有 q 个），都要调用 f 函数，然后对于每一个 queries 中的字符串，又要遍历 words 数组（假设有 w 个）中的每一个字符串并调用 f 函数。所以整体的时间复杂度为 $O(q\times n+q\times w\times n )$ ，简化后为 $O(qn+qwn)$ ，其中 n 是字符串的平均长度。如果 q、w 和 n 都比较大，时间复杂度会比较高，在处理大规模数据时可能会出现性能问题。

2. 空间复杂度

算法中主要的空间开销是用于存储结果的 answer 数组。answer 数组的长度与 queries 数组的长度相同，假设 queries 数组的长度为 q ，那么空间复杂度为 $O(q)$ 。除此之外，算法中使用的临时变量如 minChar、count、queryFreq、smallerCount、wordFreq 等，它们所占用的空间都是常数级别的，不会随着输入规模的增大而增加。所以，总的空间复杂度为 $O(q)$ 。

五、总结与拓展

通过解决这道字符串最小字母频次统计与比较的问题，我们深入学习了字符串的遍历、字符比较以及数组的操作。在实际编程中，类似的字符串处理场景非常常见，比如文本分析、数据清洗等。掌握这类问题的解法，能够为我们解决更复杂的实际问题奠定坚实的基础。

对于这道题，我们还可以进一步思考优化的方向。例如，在计算 f 值时，由于每个字符串的 f 值是固定的，我们可以在第一次计算后将其存储起来，避免重复计算，从而提高算法的效率。另外，在比较 queries 和 words 数组的 f 值时，也可以考虑使用更高效的数据结构或算法，比如排序后使用二分查找，这样可以将时间复杂度从 $O(qwn)$ 降低到 $O(qw\log w)$ ，大大提升算法在大规模数据下的性能。