牛客网算法题目-单词接龙题解

川长思鸟来 2022-12-28 07:22 140阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入描述
     *  输出描述
     *  输入
     *  输出
     *  说明
 *  原题
 *   *  算法分析
     *  解题标程

--------------------

# 题目描述 #

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

## 输入描述 ##

> 输入的第一行为一个单独的整数n(n ≤ 20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

## 输出描述 ##

> 只需输出以此字母开头的最长的“龙”的长度

## 输入 ##

5
    at
    touch
    cheat
    choose
    tact
    a

## 输出 ##

## 说明 ##

> 连成的“龙”为atoucheatactactouchoose

--------------------

# 原题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

链接：https://ac.nowcoder.com/acm/problem/16758  
来源：牛客网

--------------------

## 算法分析 ##

DFS深度优先搜索算法，相比迷宫解法而言要更加复杂。  
假设每个字符串为迷宫里的一个结点，那么我就要去通过遍历每个结点来得到一个最长的路径，对于下一个结点是否能走取决于是否能够与当前位置串形成一个“接龙”，**并且每个字符串只能使用两次**。  
因此在每次遍历的过程中去寻找最长的情况，但这里就存在一个问题：*当字符串为tact与tact时，会出现两种情况的接龙：1、tact 2、tactact*，很明显第二种是符合题意的最长接龙，**因此我还要遍历两个串进行匹配，在匹配结果找到最长的情况。**  
当这个结果到了尽头，那么我就需要**回溯**，**将字符串的使用次数和当前的累计接龙长度进行还原**

## 解题标程 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX(x,y) x>y?x:y
    char a[25][105];
    int ans=0;
    int used[25];
    int now=1;
    int n;
    
    void dfs(int k)
    {
        
        ans=MAX(ans,now);
        //循环每一个字符串
        for(int i=1;i<=n;i++){
        
            //串最多用两次
            if(used[i]<2){
        
                // i 为后接串，k 为当前需要接龙的串
                for(int j=0;j<strlen(a[k]);j++){
        
                    //当i满足接龙条件：i的第一个字符等于k中的字符时，去匹配后续字符
                    if(a[i][0]==a[k][j]){
        
                        int l1=0;
                        int l2=j;
                        //匹配后续字符
                        while(a[i][l1]==a[k][l2]&&l2<strlen(a[k])){
        
                            l1++;
                            l2++;
                        }
                        //后续字符也匹配成功
                        if(l2>=strlen(a[k])){
        
                            now+=strlen(a[i])-l1; // i 已经重合接上了 l1 长度，那么 l1多出来的部分就为多加的接龙长度
                            used[i]++;
                            dfs(i); //以i为结点继续寻找下一个可接龙串
                            //回溯
                            now-=strlen(a[i])-l1;
                            used[i]--;
                        }
                    }
                }
            }
        }
    }
    int main()
    {
        
        scanf("%d",&n);
        
        memset(used,0,sizeof(used));
        for(int i=1;i<=n;i++)
            scanf("%s",a[i]);
        scanf("%s",a[0]);   //将a[0]默认为第一个需要接的龙
        
        dfs(0);
        
        printf("%d",ans);
        
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/b744e1f556204978b5a582ad3be6feee.png