Skip to content

Latest commit

 

History

History
156 lines (137 loc) · 3.76 KB

1035.md

File metadata and controls

156 lines (137 loc) · 3.76 KB
Raw

拼写检查 1035: 拼写检查

题目给出了一个字典，要求按照字典来检查拼写错误的单词。

题目来源

1035: 拼写检查

总时间限制: 2000ms 内存限制: 65536kB

描述

现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。 单词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

读取字典以后，按照特殊字符进行划分。可以按照输入单词的长度进行比较划分。 分别比较长度相等和差一个字母的单词，对于相差一个字母的单词，可以在较长的单词中删除一个后进行比较。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
	string str;
	vector<string> dic;
	while (cin >> str && str != "#") {
		dic.push_back(str);
	}
	int i, j;
	while (cin >> str && str != "#") {
		vector<string> sword;
		bool bc = false;
		for (i = 0; i < dic.size(); ++i) {
			if (str.length() == dic[i].length()) {
				if (str == dic[i]) {
					bc = true;
					break;
				}
				else {
					int sumDiff = 0;
					for (j = 0; j < str.length(); ++j) {
						if (str[j] != dic[i][j]) {
							sumDiff++;
						}
						if (sumDiff > 1) {
							break;
						}
					}
					if (sumDiff == 1) {
						sword.push_back(dic[i]);
					}
				}
			}
			else if (str.length() == dic[i].length() + 1) {
				for (j = 0; j < str.length(); ++j) {
					string scmp = str;
					scmp.erase(scmp.begin() + j);
					if (scmp == dic[i]) {
						sword.push_back(dic[i]);
						break;
					}
				}
			}
			else if (str.length() == dic[i].length() - 1) {
				for (j = 0; j < dic[i].length(); ++j) {
					string scmp = dic[i];
					scmp.erase(scmp.begin() + j);
					if (scmp == str) {
						sword.push_back(dic[i]);
						break;
					}
				}
			}
		}
		if (bc) {
			cout << str << " is correct" << endl;
		}
		else {
			cout << str << ":";
			for (i = 0; i < sword.size(); ++i) {
				cout << " " << sword[i];
			}
			cout << endl;
		}
	}
	return 0;
}

1035.cpp 代码长度：1361B 内存：1664kB 时间：362ms 通过率：83% 最小内存：1284kB 最短时间：50ms

字符串可以采用string类型处理，可以通过vector来存储未知长度的数组。

有任何的改进意见欢迎大家在微信平台公众号主页面留言或者发表issue。