算法|单词接龙 递归
问题描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式
【算法|单词接龙 递归】只需输出以此字母开头的最长的“龙”的长度
样例输入
5
at
touch
cheat
choose
tact
a
样例输出
23
样例说明
连成的“龙”为atoucheatactactouchoose
#include
#include
typedef struct
{
char zm[100];
int ws;
int gs;
}zm_t;
void q_max(int,int,zm_t[],int,int[][20],int*);
int keyfang(zm_t*,zm_t*);
void zhaogx(int,zm_t[],int[][20]);
void shuru(int,zm_t[]);
int main(void)
{
int n;
scanf("%d",&n);
zm_t dc[20] = {0};
shuru(n,dc);
getchar();
char tou = getchar();
int gx[20][20] = {0};
zhaogx(n,dc,gx);
int max = 0,i;
for(i = 0;
i < n;
i++)
{
if(dc[i].zm[0] == tou)
{
max = max > dc[i].ws ? max : dc[i].ws;
dc[i].gs -= 1;
q_max(i,n,dc,dc[i].ws,gx,&max);
dc[i].gs += 1;
}
}
printf("%d",max);
return 0;
}void q_max(int syg,int n,zm_t dc[],int sum,int gx[][20],int*p_max)
{
int i;
for(i = 0;
i < n;
i++)
{
if(gx[syg][i] && dc[i].gs)
{
dc[i].gs -= 1;
*p_max = sum + gx[syg][i] > *p_max ? sum + gx[syg][i] : *p_max;
q_max(i,n,dc,sum + gx[syg][i],gx,p_max);
dc[i].gs += 1;
}
}
}
int keyfang(zm_t*q,zm_t*p)
{
int i,j,max = 0;
for(i = 0;
i < q->ws-1;
i++)
{
if(p->zm[i] == q->zm[q->ws-1])
{
int flag = 1;
for(j = 0;
j <= i;
j++)
{
if(q->zm[q->ws-1-j] != p->zm[i-j])
{
flag = 0;
break;
}
}
if(flag)
{
max = i+1;
break;
}
}
}
if(max > 0)
{
max = p->ws-max;
}
return max;
}
void zhaogx(int n,zm_t dc[],int gx[][20])
{
int i,j;
for(i = 0;
i < n;
i++)
{
for(j = 0;
j < n;
j++)
{
gx[i][j] = keyfang(dc+i,dc+j);
}
}
}
void shuru(int n,zm_t dc[])
{
int i;
for(i = 0;
i < n;
i++)
{
scanf("%s",dc[i].zm);
dc[i].ws = strlen(dc[i].zm);
dc[i].gs = dc[i].ws == 1 ? 0:2;
}
}推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 简谈迪克斯特拉算法