算法标签

字符串处理、字典查找、枚举

解题思路

1. 首先将输入文件第一部分的字典单词读取并存储到合适的数据结构中，如集合或列表，便于后续快速查询。这里使用集合可以利用其高效的查找特性，平均时间复杂度为 ，方便判断单词是否存在。

2. 接着读取输入文件第二部分需要检查的单词，对于每个单词进行如下操作：

• 检查该单词是否在字典集合中，如果存在，按照输出要求，直接输出 “ 是正确的”。
• 若单词不在字典中，则通过以下三种操作尝试生成可能的替换词：
1. 删除一个字母：从单词的第一个字母开始，依次删除每个位置的字母，得到新的字符串，然后检查该字符串是否在字典集合中。例如对于单词 “abc”，依次删除得到 “bc”、“ac”、“ab” 并检查。
2. 替换一个字母：遍历单词的每个位置，用 26 个小写字母中的每一个字母替换该位置的字母，生成新的字符串后检查是否在字典集合中。比如单词 “abc”，在第一个位置替换可得到 “bbc”、“cbc” 等 26 个新字符串进行检查。
3. 插入一个字母：在单词的每个位置（包括开头和结尾）插入 26 个小写字母中的每一个字母，形成新的字符串并检查其是否在字典集合中。例如 “ab” 在开头插入字母可得到 “aab”、“bab” 等，在结尾插入可得到 “aba”、“abb” 等。
• 将找到的所有替换词按照它们在字典（输入文件第一部分）中的出现顺序输出。如果没有找到替换词，则按照要求在单词后输出冒号并紧跟换行符。

代码实现（C++）

#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<string> v;
vector<int> v2;
bool cmp(string dic,string st)
{
	int i,j,l1=dic.length(),l2=st.length();
	if(l1==l2)
	{
		for(i=0;i<l1;i++)
			if(dic[i]!=st[i])break;
		for(j=l1-1;j>=0;j--)
			if(dic[j]!=st[j])break;
		return i==j;
	}
	else if(l1-l2==1)
	{
		for(i=0;i<l2;i++)
			if(st[i]!=dic[i])break;
		for(j=i;j<l2;j++)
			if(st[j]!=dic[j+1])return 0;
		return 1;
	}
	else if(l2-l1==1)
	{
		for(i=0;i<l2;i++)
		{
			string st2=st.substr(0,i)+st.substr(i+1,l2-i-1);
			if(st2==dic)return 1;
		}
	}
	return 0;
}
int main()
{
	string st;
	int i,j,k;
	while(cin>>st)
	{
		if(st.length()==1&&st[0]=='#')break;
		v.push_back(st);
	}
	while(cin>>st)
	{
		if(st.length()==1&&st[0]=='#')return 0;
		v2.clear();
		bool t=0;
		for(i=0;i<v.size();i++)
		{
			if(v[i]==st)
			{
				t=1;
				cout<<st<<" is correct\n";
				break;
			}
			else if(cmp(v[i],st))v2.push_back(i);
		}
		if(!t)
		{
			cout<<st<<":";
			for(i=0;i<v2.size();i++)
				cout<<" "<<v[v2[i]];
			cout<<endl;
		}
	}
}