问题描述:
- 拉姆刚刚开始学习英文字母,对单词排序很感兴趣,他能够迅速确定是否可以将这些单词排列在一个列表中,使得该列表中任何单词的首字母与前一个单词的尾字母相同,力能编写一个计算机程序帮助拉姆进行判断吗?
- 函数canArrangeWords的输入包含一个整数num和一个单词arr。num表示列表中单词的数目(1<=num<=100),而arr应包含只由’a’-‘z’组成的单词(2<=arr中单词长度<=100)
- 如果列表中的单词可按照要求的方式排列,返回1;否则返回-1。在这种排列中,列表中的第一个单词可以任意字母开头,不需要满足约束条件。
- 测试用例:
- TestCase 1:Input:4, [abcd,defg,ghij,jkl] Expected Return Value:1
- TestCase 2: Input: 4,[ghij,defg,jkl,abcd] Expected Return Value:-1
问题分析:
- 1.定义两个变量,代表当前匹配通过的start和end
- 2.对于下一个word来说,有可能是首尾匹配,也有可能是尾首匹配,分别更新start和end即可。
- 3.如果下一个word跟当前不匹配,我们把当且word放入容器的尾部(因为可能会在后面完成匹配)
- 4.如此循环,所有都匹配成功,或者匹配和不匹配的单词总数超过单词总数
- 5.根据上述1-4步骤,很容易联想到用队列作为数据结构。
1 using namespace std;
2 int canArrangeWords(int num,char** arr){
3 if(num<1||num>100)
4 return -1;
5 queue<string> qs;
6 for(int i=0;i<num;i++)
7 {
8 qs.push(arr[i]);
9 int len=strlen(arr[i]);
10 if(len<2||len>100)
11 return -1;
12 }
13 int count=1;
14 int countr=0;
15 char head=qs.front().at(0);
16 char end=qs.front().at(strlen(arr[0]-1);
17 qs.pop();
18 while(!qs.empty()&&(count+countr<=num))
19 {
20 int len=strlen(qs.front().c_str());
21 if(qs.front().at(0)==end)
22 {
23 end=qs.front().at(len-1);
24 qs.pop();
25 count++;
26 }
27 else if(qs.front().at(len-1)==head)
28 {
29 head=qs.front().at(0);
30 qs.pop();
31 count++;
32 }
33 else
34 {
35 qs.push(qs.front());
36 qs.pop();
37 countr++;
38 }
39 }
40 if(count==num)
41 return 1;
42 return -1;
43 }
原文链接: https://www.cnblogs.com/cynthia-dcg/p/6820285.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/253624
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!