华为OD真题机试-英文输入法（Java）

华为OD机试真题中的“英文输入法”题目主要考察的是字符串处理、单词提取、以及基于前缀的单词联想功能。以下是对该题目的详细解析：

题目描述

主管期望你来实现英文输入法单词联想功能。具体需求如下：

• 依据用户输入的单词前缀，从已输入的英文语句中联想出用户想输入的单词。
• 按字典序输出联想到的单词序列。
• 如果联想不到，请输出用户输入的单词前缀。

注意事项

1. 英文单词联想时，区分大小写：在匹配单词前缀时，需要考虑字母的大小写。
2. 缩略形式处理：如“don’t”应判定为两个单词“don”和“t”，但在联想时通常只考虑非缩略形式的完整单词。
3. 输出要求：输出的单词序列不能有重复单词，且只能是英文单词，不能有标点符号。如果存在多个符合要求的单词，它们之间应以单个空格分割。

输入描述

输入为两行：

• 首行输入一段由英文单词和标点符号组成的语句str。
• 接下来一行为一个英文单词前缀pre。

输出描述

输出符合要求的单词序列或单词前缀。如果存在多个单词，则按字典序排列并以空格分隔；如果联想不到任何单词，则直接输出用户输入的单词前缀。

解题思路

1. 提取单词：首先，需要从输入的英文语句中提取出所有英文单词。这通常可以通过正则表达式来实现，匹配连续的字母序列（考虑大小写）。
2. 过滤和排序：然后，根据用户输入的单词前缀，过滤出所有以该前缀开头的单词。之后，按照字典序对这些单词进行排序。
3. 输出结果：最后，输出排序后的单词序列。如果没有找到任何匹配的单词，则输出用户输入的单词前缀。

0 < word.length() <= 20
0 < str.length <= 10000
0 < pre <= 20

输出描述：
字典序输出符合要求的单词序列或单词前缀，存在多个时，单词之间以单个空格分割

输入：

I love you
He	

输出 ：

He	

说明：
从用户已输入英文语句”I love you”中提炼出“I”、“love”、“you”三个单词，接下来用户输入“He”，从已输入信息中无法联想到任何符合要求的单词，因此输出用户输入的单词前缀。

输入 ：

The furthest distance in the world, 
Is not between life and death, 
But when I stand in front of you, 
Yet you don’t know that I love you.
f	

输出：
front furthest
说明：
从用户已输入英文语句”The furthestdistance in the world, Is not between life and death, But when I stand in frontof you, Yet you dont know that I love you.”中提炼出的单词，符合“f”作为前缀的，有“furthest”和“front”，按字典序排序并在单词间添加空格后输出，结果为“front furthest”。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;public class Autocomplete {public static void main(String[] args) {// String sentence = "The furthest distance in the world, Is not between life and death, But when I stand in front of you, Yet you dont know that I love you.";// prefix = "f";Scanner scanner = new Scanner(System.in);String sentence = scanner.nextLine();String prefix = scanner.nextLine();System.out.println(autocomplete(sentence, prefix));}/*** 根据给定的句子和前缀，提供一个自动补全的方法* 该方法旨在从句子中提取出以给定前缀开头的单词，并按字母顺序排序后返回* 如果没有找到以给定前缀开头的单词，则直接返回前缀本身** @param sentence 完整的句子，从其中提取单词* @param prefix 需要自动补全的前缀* @return 自动补全后的单词列表，以空格分隔；如果没有可补全的单词，则返回前缀本身*/public static String autocomplete(String sentence, String prefix) {// 提取单词List<String> words = extractWords(sentence);// 过滤并排序List<String> filteredWords = filterAndSort(words, prefix);// 输出结果if (!filteredWords.isEmpty()) {return String.join(" ", filteredWords);} else {return prefix;}}/*** 从句子中提取单词列表* 该方法使用正则表达式来识别句子中的单词，并将其存储在列表中** @param sentence 待处理的句子* @return 包含句子中所有单词的列表*/private static List<String> extractWords(String sentence) {// 使用正则表达式提取单词Pattern pattern = Pattern.compile("\\b[A-Za-z]+\\b");// 创建匹配器Matcher matcher = pattern.matcher(sentence);List<String> words = new ArrayList<>();// 循环匹配while (matcher.find()) {words.add(matcher.group());}return words;}/*** 过滤并排序字符串列表* 该方法用于接收一个字符串列表和一个前缀字符串，过滤出以该前缀开头的字符串列表，并对其进行排序** @param words   字符串列表，用于过滤和排序* @param prefix  前缀字符串，用于确定过滤条件* @return        返回过滤并排序后的字符串列表*/private static List<String> filterAndSort(List<String> words, String prefix) {// 初始化一个新的字符串列表，用于存储过滤后的单词List<String> filteredWords = new ArrayList<>();// 遍历输入的字符串列表for (String word : words) {// 检查当前单词是否以指定的前缀开头if (word.startsWith(prefix)) {// 如果是，将其添加到过滤后的列表中filteredWords.add(word);}}// 对过滤后的字符串列表进行排序filteredWords.sort(String::compareTo);// 返回过滤并排序后的字符串列表return filteredWords;}}