history IntelliJ IDEA docker安装部署 Kotlin safari ios5 flowjs alertifyjs vue最新版本 solidworks图库 判断bigdecimal是否为空 xshell搭建ss pythonsocket编程 python多线程编程 python创建数据库 input函数python python教程 python排序 javaqueue java重写和重载 javaforeach java获取当前月 java列表 网站数据分析工具 梦幻西游手游助手 onenote2003 js倒计时代码 beatedit spoonwep 隐藏进程 通讯录管理系统 js倒计时 c语言编程实例 p6软件 画图怎么添加文字 证书小精灵 pr书写效果 头条视频解析 ajaxpro stata
当前位置: 首页 > 学习教程  > 编程语言

Acwing---1117. 单词接龙 (Java)_/DFS模板

2021/2/13 20:03:31 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

1117. 单词接龙 ①. 题目②. 思路③. 学习点④. 代码实现原题链接 ①. 题目 ②. 思路 这题太恶心了,再DFS深搜前,还得将每两个字符的重合最短长度给算出来,对于没有重合的两个字符肯定不符合规则,初始都是为0,两层for…

1117. 单词接龙

  • ①. 题目
  • ②. 思路
  • ③. 学习点
  • ④. 代码实现

原题链接

①. 题目

在这里插入图片描述

②. 思路

  • 这题太恶心了,再DFS深搜前,还得将每两个字符的重合最短长度给算出来,对于没有重合的两个字符肯定不符合规则,初始都是为0,两层for循环将所有单词进行最短重合路径找出,还有个技巧,就是使用字符串截取的Api进行快速判断,找到直接跳出(长度从小到大进行找)。还有一个点,每个单词都可以使用两次,我们还得开一个数组进行记录使用的次数,方便DFS后面的回溯操作, dfs(String drgon,int last),dragon表示当前的单词龙,last表示上一个连接到字符串的单词的下标。每次dfs都要进行比较长度,将最大长度进行更新

③. 学习点

④. 代码实现

import java.util.Scanner;

public class _1117_单词接龙_DFS {
	static int N=21;
	static int n;
	static String[] word=new String[N];
	static int[][] g=new int[N][N];//表示i位置子符串与j位置子符串拼接重合的最小长度
	static int[] used=new int[N];//i位置的字符串的使用次数
	static int res=0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for (int i = 0; i <n; i++) {
			word[i]=sc.next();
		}
		String start=sc.next();
		//将每两个单词计算出他们的重合长度
		for (int i = 0; i <n; i++) {
			for (int j = 0; j < n; j++) {
				String a=word[i];
				String b=word[j];
				for (int k = 1; k <Math.min(a.length(), b.length()); k++) {
					int lenA=a.length();
					int lenB=b.length();
					if(a.substring(lenA-k, lenA).equals(b.substring(0, k))) {
						//子符串拼接重合的最小长度
						g[i][j]=k;
						break;
					}
				}
			}
		}
		for (int i = 0; i <n; i++) {
			 //若该单词的第一字母和start相同
			if(word[i].substring(0,1).equals(start)) {
				used[i]++;
				dfs(word[i],i);
			}
		}
		System.out.println(res);
	}
	//dragon表示当前的单词龙,last表示上一个连接到字符串的单词的下标
	static void dfs(String drgon,int last) {
		res=Math.max(drgon.length(), res);
		
		//使用上一个单词和单词表的有剩余次数的单词进行拼接
		for (int i = 0; i < n; i++) {
			if(g[last][i]>0&&used[i]<2) {
				//重复的长度
				int k=g[last][i];
				used[i]++;
				dfs(drgon+word[i].substring(k),i);
				//回溯
				used[i]--;
			}
		}
	}
}

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_700374.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?