【最新华为OD机试E卷】英文输入法(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🍄 英文输入法

问题描述

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_suggesti