01035: 拼写检查

现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词A与单词B相似的情况有三种：

1、删除单词A的一个字母后得到单词B；

2、用任意一个字母替换单词A的一个字母后得到单词B；

3、在单词A的任意位置增加一个字母后得到单词B。

你的任务是发现词典中与给定单词相同或相似的单词。

输入

第一部分是词典中的单词，从第一行开始每行一个单词，以"#"结束。词典中的单词保证不重复，最多有10000个。第二部分是需要查询的单词，每行一个，以"#"结束。最多有50个需要查询的单词。词典中的单词和需要查询的单词均由小写字母组成，最多包含15个字符。

输出

按照输入的顺序，为每个需要检查的单词输出一行。如果需要检查的单词出现在词典中，输出“?x is correct"，?x代表需要检查的单词。如果需要检查的单词没有出现在词典中，则输出"?x: ?x1 ?x2 ...?xn"，其中?x代表需要检查的单词，?x1...?xn代表词典中与需要检查的单词相似的单词，这些单词中间以空格隔开。如果没有相似的单词，输出"?x:"即可。

样例输入

i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#

样例输出

me is correct
aware: award
m: i my me
contest is correct
hav: has have
oo: too
or:
i is correct
fi: i
mre: more me

python

def is_correct(word, dictionary):
    # 检查单词是否在字典中
    return word in dictionary

def similar(word, dict_word):
    # 检查word与dict_word是否相似，依据三种规则
    len_word = len(word)
    len_dict_word = len(dict_word)

    # 1. 删除一个字母
    if len_word - 1 == len_dict_word:
        for i in range(len_word):
            if word[:i] + word[i+1:] == dict_word:
                return True
    
    # 2. 替换一个字母
    if len_word == len_dict_word:
        diff_count = 0
        for i in range(len_word):
            if word[i] != dict_word[i]:
                diff_count += 1
            if diff_count > 1:
                return False
        if diff_count == 1:
            return True

    # 3. 插入一个字母
    if len_word + 1 == len_dict_word:
        for i in range(len_dict_word):
            if word == dict_word[:i] + dict_word[i+1:]:
                return True

    return False

def check_words(dictionary, queries):
    results = []
    
    for word in queries:
        if is_correct(word, dictionary):
            results.append(f"{word} is correct")
        else:
            similar_words = []
            for dict_word in dictionary:
                if similar(word, dict_word):
                    similar_words.append(dict_word)
            if similar_words:
                results.append(f"{word}: " + " ".join(similar_words))
            else:
                results.append(f"{word}:")
    
    return results

def main():
    # 读入词典部分
    dictionary = []
    while True:
        word = input().strip()
        if word == '#':
            break
        dictionary.append(word)

    # 读入查询部分
    queries = []
    while True:
        word = input().strip()
        if word == '#':
            break
        queries.append(word)

    # 检查单词
    results = check_words(dictionary, queries)
    
    # 输出结果
    for result in results:
        print(result)

if __name__ == "__main__":
    main()

01035: 拼写检查 ​

01035: 拼写检查