一、题目

1
2
3
4
5
6
7
8
9
主管期望你来实现英文输入法单词联想功能，需求如下：

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

英文单词联想时区分大小写
缩略形式如"don't" 判定为两个单词 "don"和 "t"
输出的单词序列不能有重复单词，且只能是英文单词，不能有标点符号

二、输入

1
2
3
4
5
6
输入两行
首行输入一段由英文单词word和标点构成的语句str
接下来一行为一个英文单词前缀pre
0 < word.length() <= 20
0 < str.length() <= 10000
0 < pre.length() <= 20

三、输出

1
2
输出符合要求的单词序列或单词前缀
存在多个时，单词之间以单个空格分割

四、示例

示例一

1
2
3
4
5
6
输入：
I love you
He

输出：
He
  • 说明：
    用户已输入单词语句”I love you”,
    中提炼出”I”,”love”,”you”三个单词
    接下来用户输入”He” ，
    从已经输入信息中无法联想到符合要求的单词
    所以输出用户输入的单词前缀

示例二

1
2
3
4
5
6
输入：
The furthest distance in the world,Is not between life and death,But when I stand in front or you,Yet you don't know that I love you.
f

输出：
front furthest
  • 说明
    满足条件的单词有 furthest 和 front，题目要求按字典序排序输出，结果为 front furthest

五、题解

本题需要先审题。一开始可能想到用 tried 树的数据结构，能解决但是有点杀鸡用牛刀的感觉。看别人的题解觉得很简洁，要求工程能力比较强。

核心功能包括分词和前缀匹配，其他包括去重。

分词一种简洁的方式是通过正则表达式。\\W表示非字母和数字的字符，等价于[^a-zA-Z0-9],这个一行语句省掉大量的字符处理的代码，强调的工程落地能力。

5.1 Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package org.stone.study.algo.ex202411;

import java.util.*;

/**
 * 主管期望你来实现英文输入法单词联想功能，需求如下：
 *
 * 依据用户输入的单词前缀，从已输入的英文语句中联想出用户想输入的单词。
 * 按字典序输出联想到的单词序列，如果联想不到，请输出用户输入的单词前缀。
 * 注意
 *
 * 英文单词联想时区分大小写
 * 缩略形式如"don't" 判定为两个单词 "don"和 "t"
 * 输出的单词序列不能有重复单词，且只能是英文单词，不能有标点符号
 */
public class EnglishInput {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // The furthest distance in the world,Is not between life and death,But when I stand in front or you,Yet you don't know that I love you.
        String words = scanner.nextLine();
        // 待搜素的单词：f
        String word = scanner.nextLine();
        List<String> ans = search(words, word);

        // front furthest
        System.out.println(String.join(" ", ans));
    }

    private static List<String> search(String words, String word) {
        // 按非单词字符分词
        String[]  wordArr = words.split("\\W+");
        // 支持字典序排序
        TreeSet<String> wordSet = new TreeSet<>(Arrays.asList(wordArr));

        List<String> ans = new ArrayList<>();
        // 遍历字典，找到符合条件的单词
        for(String wordStr : wordSet) {
            if(wordStr.startsWith(word)) {
                ans.add(wordStr);
            }
        }

        return ans.isEmpty() ? Collections.singletonList(word) : ans;
    }
}

5.2 Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import re

# 从words字符串分词并查找以word开头的单词列表
def search(words, word):
    # 使用正则表达式分割单词，\w匹配字母、数字或下划线
    word_set = {w for w in re.split(r'\W+', words) if w}

    # 使用列表推导式查找以word开头的单词
    res = [w for w in word_set if w.startswith(word)]

    # 如果没有找到任何匹配项，添加word
    if not res:
        res.append(word)

    return res

if __name__ == '__main__':
    # The furthest distance in the world,Is not between life and death,But when I stand in front or you,Yet you don't know that I love you.
    words = input()
    # f
    word = input()
    ans = search(words, word)
    # front furthest
    print(' '.join(sorted(ans)))