华为OD机考：单词接龙C++实现_c++头歌最短单词接龙

华为OD机考：单词接龙

题目描述：

单词接龙的规则是
可用于接龙的单词 首字母必须要与前一个单词的尾字母相同
当存在多个首字母相同的单词时，取长度最长的单词
如果长度也相等，则取字典序最小的单词
已经参与接龙的单词不能重复使用
现给定一组全部由小写字母组成的单词数组
并指定其中一个单词为起始单词
进行单词接龙
请输出最长的单词串
单词串是单词拼接而成的中间没有空格

输入描述

​ 输入第一行为一个非负整数
​ 表示起始单词在数组中的索引k
​ 0<=k<N
​ 输入的第二行为非负整数N
​ 接下来的N行分别表示单词数组中的单词

输出描述

输出一个字符串表示最终拼接的单词串

示例

    0
    6
    word
    dd
    da
    dc
    dword
    d

    输出
    worddwordda
    说明 先确定起始单词word 在接dword
    剩余dd da dc 则取da

   示例2
    4
    6
    word
    dd
    da
    dc
    dword
    d

    输出
    dwordda

    单词个数1<N<20
    单个单词的长度  1~30
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

C++代码

//
// Created by HANWENKE on 2022/8/29.
//
#include <map>
#include <iostream>
#include <vector>
#include <string>
#include <set>
/*思想：
 * 集合的底层是红黑树是有序的--遍历vector将每个字符串的首字符和目标字符相比较
 * 如果其相等那么就加入集合中，在集合中其会按照字典序排列
 * 题目要求单词长度相同的时取字典序最小的单词，所以判断条件时>len
 * 首字符相同取长度最常的单词
 * 注意：set不可以像vector那样通过下标访问--可以通过其迭代器来进行
 * 给迭代器解引用获取其值
 * vector删除不能够指定具体的元素,需要从其开始迭代器加上对应的下标*/
using  namespace  std;
int main(){
    vector<string>arr;
    arr.reserve(21);
    int k,n;
    cin>>k;
    cin>>n;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        arr.push_back(s);
    }
    string head=arr[k];//第一个字符串
    string builder="";//目标字符串
    builder+=head;
    arr.erase(arr.begin()+k);
    //尾部字符
    char tail=head[head.length()-1];
    while(true){
        set<string>use;
        for(int i=0;i<arr.size();i++){
 
            string word=arr[i];
            //如果当前字符串的第一个字符等于末尾字符就将其加入到set中
            if(word[0]==tail){
                use.insert(word);
            }
        }
        //如果不存在单词的第一个字母与当前字符串最后一个字符相同时-结束循环
        if(use.size()==0)break;
        //因为use.begin时一个迭代器，所以要对其解引用
        string first=*(use.begin());
        int len=first.length();
        string aim="";
        //从首字符相同的字符串中找到最长的
        for(auto it=use.begin();it!=use.end();it++){
            if((*it).length()>len){
                len=(*it).length();
                aim=(*it);
            }
        }
        //清空use当中的元素
        use.clear();
        string into;//要链接的字符串
        //判断最后的长度是否与第一个相等，如果相等就链接第一个，否则就链接aim
        if(first.length()==len){
            into=first;
        }else{
            into=aim;
        };
        tail=into[into.length()-1];
        builder+=into;
        //要删除具体的字符--首先要获得其对应的下标
        int i=0;
        for(;i<arr.size();i++){
            if(arr[i]==into){
                break;
            }
        }
        arr.erase(arr.begin()+i);
    }
    cout<<builder;
}
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