华为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;
    }

}