英文输入法

题目描述

主管期望你来实现英文输入法单词联想功能.

需求如下:

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

注意:

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

输入描述

输入为两行:

• 首行输入一段由英文单词word和标点符号组成的语句str
• 接下来一行为一个英文单词前缀pre.
  • 0 < word.length() <= 20
  • 0 < str.length <= 10000
  • 0 < pre <= 20

输出描述

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

示例1

输入:

I love you
He

输出:

He

示例2

输入:

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

题解

Python

import string


def main():
    # 首先解析出所有的单词, 忽略掉空格以及标点等, 并生成一个集合, 以备查询
    #   1. 区分大小写
    #   2. 如果有'的话, 会被作为两个单词
    #
    # 然后将前缀字符串在集合中查找, 找到以此开头的;
    # 当然, 如果考虑速度的话, 可以将单词存放列表, 并排序, 这样就可以用二分法;
    # 或者生成一个字典树 trie tree, 查找前缀的速度会更快.

    sentence = input()
    prefix = input()

    # 使用转换表, 将所有的标点都转换成空格,
    # 然后以空格为分隔, 得到所有的单词
    sentence = sentence.translate(str.maketrans(string.punctuation, " " * len(string.punctuation)))
    words = set(sentence.split())
    #print("dict:", words)

    ans = []
    for word in words:
        if word.startswith(prefix):
            ans.append(word)

    ans.sort()
    if ans:
        print(" ".join(ans))
    else:
        print(prefix)


if __name__ == "__main__":
    main()