java - 如何使用Java验证输入2是否可以使用输入1中的单词构造？

Question

假设我们有两个文本输入。 “input1”是小说中的一页。 “输入 2”是一个随机句子“你好吗？”。我需要验证这个输入 2 是否可以使用输入 1 中的单词来构造。对于这个问题，我唯一能想到的解决方案是这样的。

第 0 步: 创建一个 boolean 标志并将值设置为 true。

step1:将第一个输入拆分为标记，并将每个单词出现的次数存储在 HashMap 中。

step2:将第二个输入拆分为标记并遍历标记。

step3: 在循环内，检查 map 中是否存在当前标记。如果不是，则将 boolean 标志设置为 false 并退出循环。如果是，请检查从 Map 返回的条目的值。如果为零，则将 boolean 标志设置为 false 并退出循环。如果值为 1 或更大，则将其减 1 并继续循环。

step4:循环完成后，返回 boolean 标志的值。

如您所见，如果输入很大，步骤 1 和步骤 3 可能需要很长时间。解决这个问题的替代方法有哪些可以有更好的运行时间？

Answer 1

您正在成为“过早优化”的牺牲品(查找)。你的方法是合理的，实现一些东西，看看它是如何执行的。您会惊讶于 Java Map 的速度有多快，而且拆分成标记(单词)也不会耗时。

只有在您确定存在性能问题后才担心优化，然后仅优化您的分析工作确定为有问题的代码。任何其他方法都是在浪费您的时间，这比几万亿个 CPU 周期要昂贵得多。

根据评论中的额外信息进行编辑:

如果您知道目标短语(问题中的“随机句子”)总是比正文短很多，则可以进行改进。反转解决方案并将目标词放入 Map 并在扫描正文时使用类似的算法。您的搜索空间会更小，一旦在正文中找到足够多的单词，您就可以停止。

但是，只有当目标短语始终比未明确指定的正文短时，这种方法才会更快。对于指定数量级的文本大小(一页和一句话)，性能差异几乎无法衡量。