[数据结构与算法]洛谷 P1019 单词接龙（深度优先搜索+回溯）

题目描述

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

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

只需输出以此字母开头的最长的“龙”的长度。
输入输出样例
输入

5
at
touch
cheat
choose
tact
a

输出

23

说明/提示
样例解释：连成的“龙”为 atoucheatactactouchoose。
n≤20

思路

整体思路:搜索所有合法的连接方式，取其中最长的即可：
1.对于当前单词，考虑哪些单词可以拼接在其后面？
很显然，假设前一个单词的某一个后缀与后面单词的某一个前缀相同，则前一个单词和后一个单词可以拼接。

2.如何搜索合法的拼接方案？
对于当前单词head，我们依次构造它的后缀head.substring(i)，对于每一个后缀head.substring(i)，我们依次在“单词表”中找到前缀与head.substring(i)相等的单词word[j]拼接在head后面。之后，把word[j]做为“当前单词”继续找（搜索）可以拼接在后面的单词即可。

3.构造拼接成的单词text:
每次把word[j]拼在head后面时，只需把word[j]中除去前缀的部分拼在后面。即text变成text+word[j].substring(last.length)

java代码

//详见注释：
import java.util.Scanner;
public class Main{
    private static int res=0;   //记录最长的连接长度
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String []word=new String[N];   //N个单词
        int  []hash =new  int[N];     //hash[i]表示第i个单词用了几次
        for (int i = 0; i < N; i++){
            word[i] = sc.next();
        }
        String ch=sc.next();  //ch为开头的字母
      //字母ch为搜索的起点，因为不能有“包含”关系
      //所以在ch前加一个字母构成head以统一搜索的形式———不用特判起点字母
        String head="a"+ch;  
        String text="";   //记录单词接龙的结果
        dfs(head,word,hash,text);

      //拼接的结果text中不含第一个字母，所以res要加1（text为空则不用加）
        if(res==0) System.out.println(res);
        else System.out.println(res+1);
    }
    
     /*
     dfs函数：
     head:当前的起点单词
     word：单词数组
     hash:hash[i]表示单词word[i]用了几次
     text：记录单词接龙的结果
    */
   
    private static void  dfs(String head,String []word,int []hash,String text){
          res=Math.max(res,text.length());    //更新长度
          //System.out.println(text);
          for(int i=1;i<head.length();i++)
          {    //枚举当前单词head的可能后缀last
               String last=head.substring(i);  //last表示当前单词的后缀
              //在单词数组word中找可以拼接在当前单词后面的单词
               for(int j=0;j<word.length;j++)
               {     //若单词的长度小于等于last则不能拼接
                     if(word[j].length()<=last.length()) continue;
                     //若单词使用次数超过两次，则不能再用
                     if(hash[j]>=2) continue; 
                     //若后面单词的前缀和当前单词的后缀相同，则可以拼接
                     if(last.equals(word[j].substring(0,last.length()))){
                          //word[j]使用次数加一次
                          hash[j]++; 
                          dfs(word[j],word,hash,text+word[j].substring(last.length()));
                          hash[j]--;  //回溯时撤销“对word[j]的使用”
                     }
               }
          }
    }
}