刷题笔记合集🔗

英文输入法

问题描述

K小姐是一家科技公司的产品经理,她最近负责开发一款英文输入法。其中一个重要功能是单词联想,即根据用户输入的单词前缀,从已输入的英文语句中联想出用户想输入的单词,并按字典序输出联想到的单词序列。如果无法联想到任何单词,则输出用户输入的单词前缀。

在实现这个功能时,需要注意以下几点:

1. 英文单词联想时区分大小写。
2. 缩略形式如 "don't" 应被视为两个单词 "don" 和 "t"。
3. 输出的单词序列中不能有重复单词,且只能包含英文单词,不能包含标点符号。

输入格式

输入包含两行:

第一行是一个由英文单词 和标点符号组成的语句 。

第二行是一个英文单词前缀 。

输出格式

输出符合要求的单词序列或单词前缀,如果有多个单词,则用单个空格分隔。

样例输入1

I love you
He

样例输出1

He

样例输入2

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

样例输出2

front furthest

数据范围

题解

正则表达式

这道题目的核心在于如何有效地从给定的英文句子中提取单词,并根据给定的前缀进行匹配和排序。解题思路如下:

1. 单词提取: 使用正则表达式或字符串分割方法将输入的句子拆分成单词列表。这一步需要注意处理缩略形式,如 "don't" 应被拆分为 "don" 和 "t"。

2. 前缀匹配: 遍历提取出的单词列表,找出所有以给定前缀开头的单词。这里需要注意大小写敏感的匹配。

3. 去重和排序: 将匹配到的单词去重,然后按字典序排序。

4. 结果输出: 如果找到匹配的单词,则输出排序后的单词列表;如果没有找到匹配的单词,则输出原始前缀。

这个解法的时间复杂度主要取决于单词提取和排序的过程。假设输入句子的长度为 ,提取出的不重复单词数量为 :

• 单词提取的时间复杂度为
• 排序的时间复杂度为

总的时间复杂度为 ,这对于给定的数据范围()来说是可以接受的。

在实现时,可以使用哈希集合来实现去重,这样可以在保持时间复杂度的同时提高效率。对于前缀匹配,可以使用简单的字符串比较,也可以考虑使用更高级的数据结构如字典树(Trie)来优化大规模数据的查找效率。

参考代码

• Python

import re

def word_suggestion(sentence, prefix):
    # 使用正则表达式提取所有单词，转换为小写以便比较
    words = re.findall(r'\w+', sentence.lower())
    
    # 创建一个集合来存储匹配的单词，自动去重
    matched_words = set()
    
    # 遍历所有单词，查找匹配前缀的单词
    for word in words:
        if word.startswith(prefix.lower()):
            matched_words.add(word)
    
    # 如果没有匹配的单词，返回原始前缀
    if not matched_words:
        return prefix
    
    # 将匹配的单词排序并用空格连接
    return ' '.join(sorted(matched_words))

# 读取输入
sentence = input()
prefix = input()

# 调用函数并输出结果
print(word_suggestion(sentence, prefix))

// 待补充

• Java

/**
 * 单词建议函数
 * @param {string} sentence - 输入的句子
 * @param {string} prefix - 前缀
 * @return {string} - 匹配的单词或原始前缀
 */
function wordSuggestion(sentence, prefix) {
    // 使用正则表达式提取所有单词，转换为小写以便比较
    const words = sentence.toLowerCase().match(/\w+/g) || [];
    
    // 过滤并排序匹配前缀的单词
    const matchedWords = words
        .filter(wor