题解 | #烘焙店的配方检查#

题目链接

烘焙店的配方检查

题目描述

一家烘焙店的招牌蛋糕制作严格遵循一个固定的主配方。为了提高效率，店里准备了多种半成品配料包。现在，需要从一批配料包中，快速找出所有与主配方“兼容”的配料包。

兼容条件： 一个配料包是“兼容的”，当且仅当该配料包中的原料种类和顺序，与主配方的起始部分完全一致。换言之，配料包字符串必须是主配方字符串的一个前缀。

任务要求：

统计每一种兼容配料包在输入中出现的次数。
按照“完整度”从高到低对结果进行排序并输出。“完整度”由配料包的原料数量决定，即字符串长度越长，完整度越高。
如果没有任何配料包是兼容的，则单独输出一行 null。

输入描述：

输入为一行由空格分隔的字符串。第一个字符串是主配方，后续所有字符串是待检查的配料包。

输出描述：

输出所有兼容的配料包及其出现次数，每个占一行，格式为 配料包字符串出现次数。
输出结果需按照完整度从高到低（即字符串长度从长到短）排列。

解题思路

本题的核心任务是字符串前缀匹配、频次统计和自定义排序。可以分解为以下几个步骤：

解析输入：
- 读取完整的一行输入。
- 按空格分割字符串，得到一个字符串列表。
- 列表的第一个元素是 主配方 (main_recipe)，其余元素构成 配料包列表 (packages)。
筛选与统计：
- 创建一个哈希映射（Map 或 Dictionary）来存储兼容配料包的出现次数，键为配料包字符串，值为其出现次数。
- 遍历 配料包列表 中的每一个 配料包 (package)。
- 对于每个 package，使用字符串的 startsWith() 方法检查 main_recipe 是否以该 package 开头。
- 如果检查结果为真，说明该 package 是兼容的。将其加入到哈希映射中，并更新其计数值。
处理空结果：
- 遍历完所有配料包后，检查哈希映射是否为空。
- 如果为空，说明没有找到任何兼容的配料包，此时直接输出 "null" 并结束程序。
排序与输出：
- 如果哈希映射不为空，需要对结果进行排序。
- 将哈希映射中的键值对（entry 或 item）转换为一个列表。
- 对该列表进行自定义排序。排序规则是按照键（配料包字符串）的长度进行降序排列。
- 遍历排序后的列表，按照 配料包字符串出现次数 的格式逐行输出结果。

这种方法结合了哈希映射高效的查找和更新能力以及自定义排序的灵活性，能够清晰地解决问题。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <algorithm>

using namespace std;

// 自定义比较函数，用于按字符串长度降序排序
bool comparePairs(const pair<string, int>& a, const pair<string, int>& b) {
    return a.first.length() > b.first.length();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string line;
    getline(cin, line);

    stringstream ss(line);
    string main_recipe;
    ss >> main_recipe;

    map<string, int> compatible_counts;
    string package;
    while (ss >> package) {
        // 使用 string::rfind 检查是否为前缀
        if (main_recipe.rfind(package, 0) == 0) {
            compatible_counts[package]++;
        }
    }

    if (compatible_counts.empty()) {
        cout << "null" << endl;
    } else {
        vector<pair<string, int>> sorted_packages(compatible_counts.begin(), compatible_counts.end());
        
        sort(sorted_packages.begin(), sorted_packages.end(), comparePairs);

        for (const auto& p : sorted_packages) {
            cout << p.first << " " << p.second << endl;
        }
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] parts = line.split(" ");

        if (parts.length < 2) {
            System.out.println("null");
            return;
        }

        String mainRecipe = parts[0];
        Map<String, Integer> compatibleCounts = new HashMap<>();

        for (int i = 1; i < parts.length; i++) {
            String pkg = parts[i];
            if (mainRecipe.startsWith(pkg)) {
                compatibleCounts.put(pkg, compatibleCounts.getOrDefault(pkg, 0) + 1);
            }
        }

        if (compatibleCounts.isEmpty()) {
            System.out.println("null");
        } else {
            List<Map.Entry<String, Integer>> sortedList = new ArrayList<>(compatibleCounts.entrySet());
            
            // 使用自定义比较器按键的长度降序排序
            sortedList.sort((a, b) -> Integer.compare(b.getKey().length(), a.getKey().length()));
            
            for (Map.Entry<String, Integer> entry : sortedList) {
                System.out.println(entry.getKey() + " " + entry.getValue());
            }
        }
    }
}

# 读取整行输入
line = input().split()

# 分离主配方和配料包
main_recipe = line[0]
packages = line[1:]

# 使用字典统计兼容配料包的频率
compatible_counts = {}
for pkg in packages:
    if main_recipe.startswith(pkg):
        compatible_counts[pkg] = compatible_counts.get(pkg, 0) + 1

# 检查是否有兼容的配料包
if not compatible_counts:
    print("null")
else:
    # 将字典项转换为列表
    sorted_items = list(compatible_counts.items())
    
    # 使用 lambda 函数按键（字符串）的长度降序排序
    sorted_items.sort(key=lambda item: len(item[0]), reverse=True)
    
    # 打印结果
    for item in sorted_items:
        print(f"{item[0]} {item[1]}")

算法及复杂度

算法：本题采用哈希映射进行频次统计，然后对结果进行自定义排序。
时间复杂度： $O(N \cdot L + C \log C)$ 。其中 $N$ 是配料包的总数， $L$ 是配料包的平均长度， $C$ 是兼容配料包的种类数。
- 遍历 $N$ 个配料包并进行前缀检查，总时间为 $O(N \cdot L)$ 。
- 将 $C$ 种兼容配料包从哈希映射转为列表，并进行排序，时间复杂度为 $O(C \log C)$ 。
空间复杂度： $O(C \cdot L)$ 。主要空间开销来自于存储兼容配料包及其计数的哈希映射。在最坏情况下，所有配料包都兼容且不重复，空间复杂度为 $O(N \cdot L)$ 。