锐客网

  1. 首页 > it技术 > >

#|DFS-单词接龙

题目描述 【#|DFS-单词接龙】单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beastbeast和astonishastonish，如果接成一条龙则变为beastonishbeastonish，另外相邻的两部分不能存在包含关系，例如atat 和 atideatide 间不能相连。
输入格式
输入的第一行为一个单独的整数nn (n \le 20n≤20)表示单词数，以下nn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式
只需输出以此字母开头的最长的“龙”的长度
输入
5
at
touch
cheat
choose
tact
a
输出
23
说明/提示（连成的“龙”为atoucheatactactouchoose）

import java.util.Scanner; public class 单词接龙2 { static int n,ans; static int [][]dic=new int[21][21]; static int[]vis=new int[21]; static String [] word=new String[21]; static char s; static void f(String a,String b,int x,int y) { int a1=a.length()-1,b1=b.length()-1; for(int i=0; i<=b1; i++)//从第一个开始枚举 { if(a.charAt(0)==b.charAt(i))//如果a的首字母和b的字母相同 ，则判断它们能不能接在一起 { int pos=0,tot=0; //pos是当前a的第几个字母，tot是a和b的重合部分长度 for(int j=i; j<=b1; j++) { if(a.charAt(pos)==b.charAt(j)) { tot++; pos++; if(j==b1&&tot!=Math.min(a1,b1)+1) //如果枚举到了最后，并且a和b没有包含关系，说明可以这么接 dic[x][y]=tot; //记录最小重叠部分的长度 //之所以不break，是因为后面可能还会枚举到更小的接法 //比如 chsese 和 sesettt 显然 chsesesettt 要比chsesettt更优 } else break; } } } } static void dfs(int pos,int sum) { ans=Math.max(ans,sum); //实时更新ans for(int i=1; i<=n; i++) { if(dic[i][pos]>0&&vis[i]>0) { vis[i]--; int suml=sum+word[i].length()-dic[i][pos]; //接上新单词"龙"的长度为=旧的长度+新单词长度-重复部分长度 dfs(i,suml); //接上新单词继续搜索 vis[i]++; } } } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); n=scanner.nextInt(); for (int i = 1; i <=n ; i++) { word[i]=scanner.next(); vis[i]=2; } s=scanner.next().charAt(0); for (int i = 1; i <=n ; i++) {//i,j 用dic记录第i个单词和第j个单词的重叠情况，例如dic[4][3]=2表示第四个接第三个重叠两个 for (int j = 1; j <=n ; j++) { f(word[i],word[j],i,j); } } for(int i=1; i<=n; i++) { if(word[i].charAt(0)==s)//找到开始部分 { vis[i]--; dfs(i,word[i].length()); //深搜 vis[i]++; } } System.out.println(ans); } }

    推荐阅读


    上一篇：Kafka生产者之重试机制

    下一篇：vue|Vue教程-Vue语法糖与v-bind绑定CSS样式-学习vue第一站深入浅出（五）