于是使用暴力搜索法了,这里的技巧是可以使用优化技术:
1 剪枝:这里直接分组搜索,分组是按照字符串的长度分组
2 对比查找是合法字符的时候不要使用Edit Distance,而是使用计算字符差别的方法判断是否是合法字符的。
有了这两个技巧就不算纯粹的暴力法了,最后速度还是挺快的。
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 10001;
const int ALP_SIZE = 26;
const int WORD_SIZE = 18;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
struct strNode
{
int num;
char str[WORD_SIZE];
bool operator<(const strNode &str) const
{
return num < str.num;
}
};
char word[WORD_SIZE];
vector<strNode> dict[WORD_SIZE];
vector<strNode> res;
int num;
inline bool getReplacing(int len, char di[])
{
int k = 0;
for (int j = 0; j < len; j++)
{
if (di[j] != word[j])
{
k++;
if (k > 1) break;
}
}
if (k < 2) return true;
return false;
}
inline bool getDel(int len, char di[])
{
int k = 0;
for (int j = 0, w = 0; j < len; j++, w++)
{
if (di[w] != word[j])
{
k++;
if (k > 1) break;
j--;
}
}
if (k < 2) return true;
return false;
}
inline bool getIns(int len, char di[])
{
int k = 0;
for (int j = 0, w = 0; w < len-1; j++, w++)
{
if (di[w] != word[j])
{
k++;
if (k > 1) break;
w--;
}
}
if (k < 2) return true;
return false;
}
int main()
{
strNode W;
while (gets(W.str))
{
for (int i = 0; i < WORD_SIZE; i++)
{
dict[i].clear();
}
num = 0;
int len = strlen(W.str);
W.num = num++;
dict[len].push_back(W);
while (gets(W.str) && W.str[0] != '#')
{
len = strlen(W.str);
W.num = num++;
dict[len].push_back(W);
}
out:
while (gets(word) && word[0] != '#')
{
len = strlen(word);
int N = (int)dict[len].size();
for (int i = 0; i < N; i++)
{
if (!strcmp(word, dict[len][i].str))
{
printf("%s is correct\n", word);
goto out;
}
}
printf("%s:", word);
res.clear();
for (int i = 0; i < N; i++)
{
if (getReplacing(len, dict[len][i].str))
{
res.push_back(dict[len][i]);
}
}
N = (int)dict[len-1].size();
for (int i = 0; i < N; i++)
{
if (getIns(len, dict[len-1][i].str))
{
res.push_back(dict[len-1][i]);
}
}
N = (int)dict[len+1].size();
for (int i = 0; i < N; i++)
{
if (getDel(len, dict[len+1][i].str))
{
res.push_back(dict[len+1][i]);
}
}
sort(res.begin(), res.end());
for (int i = 0; i < (int)res.size(); i++)
{
printf(" %s", res[i].str);
}
putchar('\n');
}
}
return 0;
}