精华内容
下载资源
问答
  • 单词接龙
    千次阅读
    2022-03-28 23:09:24

    注意!答案仅作为参考(实际考试中下列代码通过用例100%,但不代表最优解)
    单词接龙的规则是
    可用于接龙的单词 首字母必须要与前一个单词的尾字母相同
    当存在多个首字母相同的单词时,取长度最长的单词
    如果长度也相等,则取字典序最小的单词
    已经参与接龙的单词不能重复使用
    现给定一组全部由小写字母组成的单词数组
    并指定其中一个单词为起始单词
    进行单词接龙
    请输出最长的单词串
    单词串是单词拼接而成的中间没有空格

        输入描述
        输入第一行为一个非负整数
        表示起始单词在数组中的索引k
        0<=k<N
        输入的第二行为非负整数N
        接下来的N行分别表示单词数组中的单词
    
        输出描述,
        输出一个字符串表示最终拼接的单词串
    
        示例
        0
        6
        word
        dd
        da
        dc
        dword
        d
    
        输出
        worddwordda
        说明 先确定起始单词word 在接dword
        剩余dd da dc 则取da
    
       示例2
        4
        6
        word
        dd
        da
        dc
        dword
        d
    
        输出
        dwordda
    
        单词个数1<N<20
        单个单词的长度  1~30
    
    import java.util.
    更多相关内容
  • leetcode 127单词接龙

    2021-01-21 16:58:59
    单词接龙 给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则: 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明...
  • 126. 单词接龙 II

    2021-01-20 13:53:31
    126. 单词接龙单词接龙 II链接链接题目.难度难度:high解答:解答:这其实就是图的算法,Dijkstra算法这道题,先求直达的最小路径,这个用bfs没啥好说的,一般求路径的问题就是要用dfs,可是不需要求所有的到达路径,...
  • leetcode单词接龙2 LeetCode Python3 刷题记录 推荐题目列表 第一周题目列表 1两数之和 21合并两个有序链表 26删除排序数组中的重复项 42接雨水 66加一 88合并两个有序数组 189旋转数组 283移动零 第二周题目列表: ...
  • leetcode单词接龙2 这里是一只菜鸡的leetcode刷题记录 统计前已完成题目 5、6、7、8、9、11、12、17、19、23、25、30、114、1226 时间 题目 WA次数 2020-10-23 16:** 2 2020-10-23 22:52 1 2020-10-27 12:11 0 2020-...
  • leetcode单词接龙2 LeetCode 刷题记录 LeetCode JavaScript version 为提高自己 JS 的编程能力,准备开始用 JS 做 LeetCode 的题目,选择下面 10 个类型的题目。每天一道! 经过两个多月的时间完成了七十多道题目,...
  • 目前仅有界面部分: 免责声明:本站所有文章和图片均来自用户分享和网络收集,文章和图片版权归原作者及原出处所有,仅供学习与参考,请勿用于商业用途,如果损害了您的权利,请联系网站客服处理。
  • leetcode单词接龙2 数据结构和算法练习 Success belongs to the persevering! leetcode 编号 php (leetcode/php) go (leetcode/go/algo) c 001.两数之和 001.php 001.go - 002.两数相加 002.php 002.go - 003.无...
  • leetcode单词接龙2 Algorithms 算法学习笔记 目录 leetcode刷题笔记 数组 排序算法 链表 反转 关系题型整理 股票买卖 矩形面积或装水问题 子序列问题 排列组合 栈 队列 树 基础遍历 BFS DFS 回溯 动态规划
  • leetcode单词接龙2 LeetCode 题集 序号 本地链接 LeetCode链接 关键词 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 动态规划(DP) 38 DP 39 DP 40 DP ...
  • 单词接龙

    千次阅读 2021-05-09 17:22:42
    单词接龙 单词接龙是一个与我们经常玩的成语接龙相类似的游戏。 现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”,每个单词最多被使用两次。 在两个单词相连时,其重合部分合为...

    单词接龙

    单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

    现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”,每个单词最多被使用两次。

    在两个单词相连时,其重合部分合为一部分,例如 beast 和 astonish ,如果接成一条龙则变为 beastonish。

    我们可以任意选择重合部分的长度,但其长度必须大于等于1,且严格小于两个串的长度,例如 at 和 atide 间不能相连。

    输入格式

    输入的第一行为一个单独的整数 n 表示单词数,以下 n 行每行有一个单词(只含有大写或小写字母,长度不超过20),输入的最后一行为一个单个字符,表示“龙”开头的字母。

    你可以假定以此字母开头的“龙”一定存在。

    输出格式

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

    数据范围

    n≤20

    输入样例:

    5
    at
    touch
    cheat
    choose
    tact
    a
    

    输出样例:

    23
    

    提示

    连成的“龙”为 atoucheatactactouchoose。

    我们的思路是什么?
    我们先输入所有单词
    然后就看单词之间有没有重复的部分
    就是罗列两个单词,一前一后,然后开始枚举位置,从1开始枚举
    只要有重复的部分就直接break
    这里需要注意substr的用法,第一个参数是枚举的位置,第二个参数是字符串的长度
    然后开一个数组用来记录两个字符串之间的长度
    然后从头开始枚举字符串,要是字符串第一个字母和字符有重叠,那么就直接开始搜
    然后我们想想该怎么搜
    就是先搜一个字符串,然后开始枚举其他字串,然后看用来记录重叠字串的数组
    要是两个字串有重叠,也就是g数组不为空,并且前面串的使用次数不超过两次
    就开始搜,这里还用到一个substr函数,但是就只有一个参数
    表示的是这个字母后的长度
    回溯回来,使用次数-1

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    string word[10010];
    int g[1010][1010];
    int use[1010];
    char head;
    int n;
    int ans = 0;
    void dfs(string dragon,int last)
    {
    	ans = max(ans,(int)dragon.size());
    	use[last]++;
    	for(int i=1;i<=n;i++)
    	{
    		if(g[last][i] && use[i]<2)
    		dfs(dragon+word[i].substr(g[last][i]),i);  //第几个字符之后的字符串 
    	}
    	use[last]--;
    }
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>word[i];
    	cin>>head;
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    		{
    			string a = word[i],b = word[j];
    			for(int k=1;k<min(a.size(),b.size());k++)
    			if(a.substr(a.size()-k,k)==b.substr(0,k))
    			{
    				g[i][j] = k;
    				break;
    			}
    		}
    	
    	for(int i=1;i<=n;i++)
    	if(word[i][0]==head) 
    	dfs(word[i],i);
    	
    	cout<<ans<<endl;
    	return 0;	
    }

    要加油哇!!!

    展开全文
  • leetcode单词接龙2 leetcode-interview-top-plan ,刷题进度记录 计划:6/30 前刷完 100 题 超额计划:6/30 前刷完 145 题 剩余:16天 说明 进来的同学先在 README.md (也就是本文件)中添加自己的列(建议用 ...
  • 单词接龙(信息学奥赛一本通-T1220).pdf
  • 英文单词接龙

    2022-07-01 14:06:37
    单词接龙:一个单词的头和上一个单词的尾相同如:ab---ba第一个单词的头没有要求

    单词接龙:一个单词的头和上一个单词的尾相同

    如:ab---ba

    第一个单词的头没有要求

    #include<bits/stdc++.h>//单词接龙
    using namespace std;
    string b[100001];
    string l[100001];//当前龙的内容
    int c[100001];//每个单词是否用了
    int sum;//当前已经接到第几个位置
    int lenb;//所有单词的数量
    int n;//需要龙的长度
    int m;//需要多少条龙
    int ol;//第几条龙
    bool f=false;//第ol条龙是否接成功了
    void dfs(char last) { //上一个龙的结尾
    	if(sum==n+1) {
    		cout<<"第"<<++ol<<"条龙:"<<endl;
    		for(int i=1; i<n; i++) {
    			cout<<l[i]<<"---";
    		}
    		cout<<l[n];
    		f=true;
    		cout<<endl;
    		return;
    	}
    	for(int i=1; i<=lenb; i++) {
    		if(c[i]==1) {
    			continue;
    		}
    		if(b[i][0]==last||last=='!') {
    			c[i]=1;
    			l[sum]=b[i];
    			sum++;
    			dfs(b[i][b[i].size()-1]);
    			sum--;
    			if(f==true) {
    				return;
    			}
    			c[i]=0;
    		}
    	}
    }
    void change_first() {
    	sum=1;
    	f=false;
    }
    int main() {
    	cout<<"输入: @end  结束输入"<<endl;
    	string a;
    	while(cin>>a) {
    		if(a=="@end")
    			break;
    		b[++lenb]=a;
    	}
    	cout<<endl;
    	cout<<"请输入龙的长度:";
    	cin>>n;
    	cout<<endl;
    	cout<<"请输入需要多少条龙:";
    	cin>>m;
    	cout<<endl;
    	for(int i=1; i<=m; i++) {
    		change_first();
    		dfs('!');
    	}
    	if(ol==m) {
    		cout<<endl;
    		cout<<"任务成功!"<<endl;
    	} else {
    		cout<<endl;
    		cout<<"任务失败!"<<endl;
    	}
    	int wait;
    	cin>>wait;
    	return 0;
    }

    展开全文
  • 年会上玩单词接龙比赛,挑战者只能从预先准备好的词库说出里面的单词,规则是一个单词的首字母必须和上一个单词的尾字母相同,每个单词只能说一次,说完词库中所有单词即为获胜。给你一个字符串的列表表示词库,请...
  • 单词接龙1

    2022-08-08 20:31:14
    算法训练 单词接龙 时间限制:1.0s 内存限制:256.0MB 问题描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单
  • 单词接龙c++题解 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时...

    题目描述

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

    输入格式

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

    输出格式

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

    输入输出样例

    输入 #1复制

    5
    at
    touch
    cheat
    choose
    tact
    a
    

    输出 #1复制

    23
    

    说明/提示

    样例解释:连成的“龙”为 atoucheatactactouchoose

    n \le 20n≤20。

    单词接龙(题解)———hyperbole_Q

    基本思路是搜索。

    处理的难点在于对重叠部分的处理。

    单词的使用次数很好判断,开一个数组即可,和正常向dfs的vis数组差不多。

    但对于重叠部分的处理,我想细说一下。

    因为连接起来的单词要最长,所以对比是选择从上一个单词的末尾与当前单词的开头进行比对,如果发现不符那就不能匹配。

    其他的代码解释都一一使用注释的方法给各位大神标出来了。如果我讲的不够细或者还有不足,请大神手下留情勿喷,栓Q了。

    这里我使用一个check函数,用来比较两个串s和m的长度为k的接口能不能匹配。

    判断方式有两种,第一种就是我用的这样按字符比较,如果发现某处不匹配立即返回false。还有一个方法是用string里面的substr,有兴趣的同学可以试一下如果再继续拓展的话就大可不必了啊。

    我们假设接口长度为k,串s的长度为lens,然后我们从0到k枚举,判断s[lens-k+i]是不是等于m[i]。

    这个式子怎么来的呢?接口前面的串是s,后面的串是m,那么很显然,s串的接口最开始应该是lens-k处,然后在后面加上一个枚举的i就可以保证扫描到所有接口字符(我们的i是从0开始枚举的)。

    还有一些细节问题。 如果我们在接龙的时候发现我们现在要接的龙还不如之前某一次接过的长,那么这个接龙方案肯定不是最优的,所以要舍去,这个正确性是显然的。

    (想一下深搜时的遍历过程,这句话便不难理解)

    使用我这个方法,可能有一个奇怪的想法有同学没想到,那就是在进行拼接操作时,要注意使用给定的串的副本(即复制一份原来的串)进行拼接处理。

    这是因为,如果你把原串改变了,而且这个串还不是最优的,那就完了,回溯不回去了。

    具体到操作上,首先,我们从1到n枚举每个短字符串,如果它已经被用了两次则continue,然后我们求出当前短串的长度,从1到这个长度枚举,枚举的是接口的长度(自然是接口越短融合串越长嘛) 然后执行拼接操作,记录一下最大长度,再加上回溯就好了。

    拼接操作和check函数很像,具体到代码上大家就能看明白了。废话不多说,上代码,保证AC!!!(作者亲测)

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #define maxn 100//根据题目要求自调,各大网站题目可能会稍有变动
    using namespace std;
    int n;
    int ans = 0;//其实也不需要赋0,只是个人习惯而已
    string word[maxn];//字符串数组,用来存储单词
    string beginn;//用来存储开头字符
    int used[maxn];//这个就是用来记录dfs时候每一个单词被使用了几次的数组
    bool check(string s,string m,int k){//重点一,check函数判断接口可行性,k代表接口长度,以下同
        int lens = s.length();
        for (int i=0;i<k;i++){
            if(s[lens-k+i]!=m[i])//我讲过了
                return false;
        }
        return true;
    }
    void add(string &s,string m,int k){//拼接操作,因为要把m接到s上,所以对于s串不可以传参,因为我们要试图改变这个串
        int lenm = m.length();
        for (int i=k;i<lenm;i++) s+=m[i];//C++字符串类型特性操作,支持+=符号直接拼接
    }
    void dfs(string now){//这只是一个看似平淡无奇的dfs
        int x = now.length();
        ans = max(ans,x);//每次拼接之后更新一下答案
        for (int i=1;i<=n;i++){
            if (used[i]>=2)//如果有一个单词用完了,那这个单词就不能选了
                continue;
            int maxk = word[i].length();
            for (int j=1;j<=maxk;j++){//枚举接口长度
                if (check(now,word[i],j)){
                    string temp = now;//重点二,使用字符串副本进行拼接
                    add(temp,word[i],j);
                    if (temp==now)//拼完之后如果发现长度没增加,也就是和原串一样,那这次拼接没有意义,剪掉
                        continue;
                    used[i]++;
                    dfs(temp);
                    used[i]--;//这只是一个看似平淡无奇的回溯
                }
            }
        }
    }
    int main(){
        cin >> n;
        for (int i=1;i<=n;i++)cin >> word[i];
        cin >> beginn;
        dfs(beginn);
        cout << ans << endl;
        return 0; 
    }

    勿喷,作者只是一个小学生...

    展开全文
  • ybt 1220:单词接龙 ybt 1913:【00NOIP普及组】单词接龙 OpenJudge NOI 2.5 8783:单词接龙 洛谷 P1019 [NOIP2000 提高组] 单词接龙 【题目考点】 字符串处理,二维数组存储多个字符串 深搜 【解题思路】 解法1:...
  • Java 算法 单词接龙

    2022-01-08 22:45:45
    单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一...
  • 华为机试:单词接龙

    2022-06-04 11:47:07
    单词接龙的规则是 可用于接龙的单词 首字母必须要与前一个单词的尾字母相同 当存在多个首字母相同的单词时,取长度最长的单词 如果长度也相等,则取字典序最小的单词 已经参与接龙的单词不能重复使用 现给定一组全部...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,784
精华内容 1,513
关键字:

单词接龙