多轮字符串Token存入数组及ingest/appearance函数实现求助

需求梳理 #

• 实现多轮输入处理，将每次输入的完整字符串存储起来
• 实现ingest函数：接收字符串，将其存入集合
• 实现appearance函数：接收字符串前缀，返回0-1之间的归一化值，即该前缀匹配的存储字符串数量占总存储数的比例
• 分析解决方案的时空复杂度

完整代码实现 #

import java.util.ArrayList;
import java.util.Scanner;

public class PrefixCounter {
    // 用ArrayList存储所有经过ingest的字符串，支持动态扩容
    private static ArrayList<String> storage = new ArrayList<>();

    // ingest函数：将输入字符串存入集合
    public static void ingest(String input) {
        storage.add(input);
    }

    // appearance函数：计算前缀匹配的占比
    public static double appearance(String prefix) {
        if (storage.isEmpty()) {
            return 0.0;
        }
        int matchCount = 0;
        for (String str : storage) {
            if (str.startsWith(prefix)) {
                matchCount++;
            }
        }
        return (double) matchCount / storage.size();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入字符串，输入'exit'结束输入：");
        
        // 多轮输入循环
        while (true) {
            String input = scanner.nextLine().trim();
            if ("exit".equalsIgnoreCase(input)) {
                break;
            }
            // 调用ingest存储输入
            ingest(input);
        }

        // 测试示例中的appearance调用
        System.out.println(appearance("McDonal"));    // 预期输出0.8
        System.out.println(appearance("McDonal:hk")); // 预期输出0.6
    }
}

原代码问题修正说明 #

• 原代码仅处理单次输入，通过while(true)循环实现多轮输入，直到用户输入终止指令
• 原代码用固定长度数组String[] ingestWords = {}无法动态存储多轮输入，改用ArrayList<String>实现动态扩容存储
• 原代码仅拆分打印Token，实际需求是存储完整输入字符串用于前缀匹配，因此直接将整个输入传入ingest存储

时空复杂度分析 #

时间复杂度 #

• ingest函数：向ArrayList添加元素的时间复杂度为O(1)（均摊复杂度）
• appearance函数：需要遍历所有存储的字符串，时间复杂度为O(n)，其中n为存储的字符串总数
• 多轮输入处理：每轮输入处理为O(1)，总时间取决于输入次数

空间复杂度 #

• 整体空间复杂度为O(nm)*，其中n是存储的字符串数量，m是单个字符串的平均长度，用于存储所有输入的字符串

内容的提问来源于stack exchange，提问作者Matthew