博客

题意

根据给出的一个若干单词组成的字典，查询一些单词是否正确，对于在字典中打不到的单词，考虑添加、删除或者替换其中一个字母，然后在字典中查找．

分析

• 如果暴力查找，那必然会超时．因此，考虑用空间换时间，用单词长度做一个索引．

代码如下：

Memory: 980K　Time: 485MS　Length: 68LINES

#include <cstring>
#include <iostream>
using namespace std;
typedef char str_t[17];
str_t dictory[10000] = { 0 };
int dic_len[10000] = { 0 };
int position[17][10000] = { { 0 } };
int length_cnt[17] = { 0 };
inline bool cmp(char* a, char* b, int len_a, int len_b)
{
    if (len_a == len_b) {   //替换一个字母即相同
        int cnt = 0;
        for (int i = 0; i < len_a && cnt < 2; ++i) {
            if (a[i] != b[i]) {
                ++cnt;
            }
        }
        return cnt == 1;
    }
    if (len_a - len_b == 1 || len_b - len_a == 1) {    //添加或者删除一个字母即相同
        if (len_a > len_b) {
            len_a = len_b;
            swap(a, b);
        }
        a[len_a] = b[len_a + 1] = ' ';
        int i = 0, j = 0;
        for (; i < len_a + 1 && (i == j || i + 1 == j); ++i, ++j) {
            if (a[i] != b[j]) {
                --i;
            }
        }
        a[len_a] = b[len_a + 1] = 0;
        return i + 1 == j;
    }
    return false;
}

int main()
{
    int cnt = 0;
    for (cnt = 0; cin >> dictory[cnt] && dictory[cnt][0] != '#'; ++cnt) {
        dic_len[cnt] = strlen(dictory[cnt]);
        position[dic_len[cnt]][length_cnt[dic_len[cnt]]] = cnt;
        ++length_cnt[dic_len[cnt]];
    }
    str_t str = { 0 };
    while (cin >> str && str[0] != '#') {
        int i;
        int str_len = strlen(str);
        for (i = 0; i < length_cnt[str_len]; ++i) {
            if (!strcmp(str, dictory[position[str_len][i]])) {
                cout << str << " is correct" << endl;
                break;
            }
        }
        if (i < length_cnt[str_len]) {
            continue;
        }
        cout << str << ":";
        for (i = 0; i < cnt; ++i) {
            if (cmp(str, dictory[i], str_len, dic_len[i])) {
                cout << " " << dictory[i];
            }
        }
        cout << endl;
    }
    return 0;
}