每日一题——自动补全——1972

题目描述

• 奶牛贝茜买了一个新手机，并十分喜欢用它发短信。
  但是它的大蹄子在手机的小屏幕上打字时遇到了麻烦，它总是把单词拼错。
• 农夫约翰同意通过编写一个自动补全程序来帮助它，当它输入部分单词时，该应用程序可以给出补全建议。
• 自动补全程序可以访问一个包含W个单词的词典，每个单词由a…z范围内的小写字母组成，其中所有单词中的字母总数最多为1000000。
• 现在给定一个包含N个部分单词的列表，每个部分单词最多包含1000个字母。
• 对于每个部分单词i，还会提供一个整数K_i，自动补全程序需要找到词典中以部分单词i作为前缀的所有单词中，按字典序排序排在第K_i个的单词。
• 也就是说，对所有部分单词i的有效补全按字典序进行排序，输出此顺序下的第K_i个补全。

输入格式

• 第一行包含两个整数W和N。
• 接下来W行，按单词在词典中的顺序，每行描述一个单词。字典中的所有字符串均互不相同。
• 接下来N行，每行首先包含一个整数K_i，然后包含一个部分单词i。

输出格式

• 共N行，第i行输出部分单词i的第K_i个有效补全在词典中出现的位置(一个1～W之间的整数)。
• 如果第K_i个有效补全不存在，则输出—1。

输入样例

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出样例

3
1
-1
1
2
3

题目参考自AcWing

代码提交——显示超时

#include 
#include 
#include 

using namespace std;

/*
 * 自动补全单词
 * 理解：
 * 1、单纯地按照它运行地思路可以实现，先形成字典，然后在进行x
 * 2、首先字典是固定的，按照他输入的顺序进行保存的，只需要输出对应字典的位置即可
 * 3、然后找出所有前缀相同的单词，并按照字典顺序进行排序
 * 4、找出特定的单词，在原来的字典中的次序即可
 * 思路：
 * 1、首先保存原来的字典，保存为string的数组
 * 2、将数组按照字典的顺序进行排序，生成一个新的序列
 * 3、根据次序找到相同的序列即可，然后获取第一个数组的位置即可
 * 问题：
 * 1、如何构建字母字典？简单按照对应字母顺序进行排序，然后遇到了第一个逐个往后数
 * 2、然后常规的字典按照键值对进行保存，这里主要是关于字符串的比较排序问题如何实现？
 *  可以自己定义一种结构体，并设定比较的方法。
 * 参考：
 * 1、将所有的字母保存为一个树，然后在使用树的前序遍历，找到共同节点的最多子节点即可实现
 * 2、按照我上述的方法进行实现
 */

//保存原来的索引
map<const string ,int> words;
//保存字典顺序
list<string> dictSort;

/*
 * 返回自动补全的结果
 */
int solution(int valueNum,string searchValue ){

    //从前往后进行遍历对应结果
    list<string>::iterator Iterator;
    int IteratorNum = 1;
    for (Iterator = dictSort.begin(); Iterator != dictSort.end(); Iterator ++) {
        cout<<*Iterator<<" ";
        if((*Iterator).substr(0,searchValue.size()) == searchValue){
            // 往后遍历对应数量的单词
            if(IteratorNum == valueNum){
                //判定两个单词是否相同
                return words[*Iterator];
            }
            IteratorNum ++;
        }
    }

    return -1;
}

int main() {

    //获取外界输入，将输入的位置保存为value
    int dictNum;
    int searchNum;
    cin>>dictNum>>searchNum;
    for(int i = 1;i <= dictNum;i ++){
        string wordItem = "";
        cin>>wordItem;
        dictSort.push_back(wordItem);
        words[wordItem] = i;
    }
    dictSort.sort();

    //获取外界的输入，并进行查找
    for (int j = 0; j < searchNum; ++j) {
        int valueNum = 0;
        string searchValue = "";
        cin>>valueNum>>searchValue;
        cout<<solution(valueNum,searchValue);
    }


    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

原因分析

• 超时，主要是因为搜索的问题，我是逐个遍历进行搜索的，严重超时。
• 可以修改为二分查找进行实现。

优化——逐个搜索变为二分搜索

• 自己选取的数据结构list适合首尾快速插入和删除，但是不能获取任意位置的元素，所以需要替换整个数据结构。

#include 
#include 
#include 

using namespace std;

//保存原来的索引
map<const string ,int> words;
//保存字典的内容
string dictArray[30010];

//获取外界输入，将输入的位置保存为value
int dictNum;
int searchNum;

int solutionBinarySearch(int valueNum,string searchValue ){
    int L = 1,R = dictNum + 1;
    while (L < R){
        int mid = L + R >>1;
        if (dictArray[mid] >= searchValue)
            R = mid;
        else
            L = mid + 1;
    }
    //判定结果输出
    int t = R + valueNum -1;
    if (t > dictNum+1 || dictArray[t].substr(0,searchValue.size()) != searchValue)
        return -1;
    else
        return words[dictArray[t]];
}
int main() {


    cin>>dictNum>>searchNum;
    for(int i = 1;i <= dictNum;i ++){
        string wordItem = "";
        cin>>wordItem;
        words[wordItem] = i;
        dictArray[i] = wordItem;
    }
    sort(dictArray+1,dictArray + dictNum);

    //获取外界的输入，并进行查找
    for (int j = 0; j < searchNum; ++j) {
        int valueNum = 0;
        string searchValue = "";
        cin>>valueNum>>searchValue;
        cout<<solutionBinarySearch(valueNum,searchValue);
    }


    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

• 总是显示wrong Answer，但是自己对了一下输出，并没有任何问题，在官方的调试台上，显示30000，并且所有的输出都是空，说明内存溢出了，不能保存那么大的数据。

参考AcWing官方代码

//
// Created by gray on 2022/8/19.
//
#include 
#include 
#include 

// 使用pair关键字必须要使用
#define x first
#define y second

using namespace std;

typedef pair<string,int> PSI;

const int N = 30010;

int m,n;
PSI dict[N];

int main(){
    cin >> m >> n;
    for(int i = 1;i <= m;i ++){
        cin >> dict[i].x;
        dict[i].y = i;
    }

    // 进行排序
    // 不是很清楚这里的含义，为什么指定是n+1
    sort(dict+1,dict + m + 1);

    // 枚举一下每一次的询问
    while(n --){
        int k;
        string str;
        cin>>k>>str;

        //进行二分搜索
        int l = 1,r = m + 1;
        while (l < r){
            int mid = l + r >> 1;
            if(dict[mid].x >= str) r = mid;
            else l = mid + 1;
        }

        //判定结果进行输出
        int t = r + k -1;
        // 当前的序列已经超出了所有的元素的个数，或者说当前的单词并不符合对应前缀
        if(t > m || dict[t].x.substr(0,str.size()) != str)
            puts("-1");
        else
            cout << dict[t].y << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

分析与总结

• 通过构建pair类型的数据，我觉得很方便。首先，pair构成array能够按照字典顺序进行排序，很方便。然后就是通过字典顺序访问的pair元素，能够获取对应单词的补全情况和在原来的字典中的顺序。将字典和数组进行组合。
• 在上文中，涉及到排序，即需要对保存数据的结构进行随机访问，所以应该使用vector，而不是list

知识补充

vector和list的区别

• vector底层结构是使用动态顺序表，在内存中有连续的空间，支持随机访问。
• list在底层结构是带头结点的双向循环链表，在内存上不是一段连续的空间，不支持随机访问。