【python】单词接龙

题目:

这是一个关于“单词接龙”的算法题目。在这个游戏中,我们需要从给定的一组单词中,以特定的开头字母构造出一条最长的“龙”。每个单词在这条“龙”中最多出现两次。当两个单词相连时,它们的重合部分被合并成一个。例如,"beast"和"astonish"可以合并成"beastonish"。重要的是,相邻的两个单词之间不能存在包含关系,比如"at"和"atide"不能相连。

 

代码:

n = int(input().strip())
word = [input().strip() for _ in range(n)]
beginn = input().strip()

# 初始化一个列表,用于记录每个单词的使用次数
used = [0 for _ in range(n)]
# 初始化答案变量,用于存储最长字符串的长度
ans = 0

# 定义一个函数来检查两个字符串是否在给定长度k的情况下能够连接
def check(s, m, k):
    return s[-k:] == m[:k]

# 定义一个函数来连接两个字符串,从第k个字符开始连接
def add(s, m, k):
    return s + m[k:]

# 定义一个深度优先搜索函数来递归地寻找最长的字符串
def dfs(now):
    global ans
    x = len(now)
    ans = max(ans, x)
    for i in range(n):
        # 如果某个单词使用次数超过2次,则跳过
        if used[i] >= 2:
            continue
        maxk = len(word[i])
        for j in range(1, maxk + 1):
            # 如果当前字符串now和word[i]能在j长度下连接,则进行连接
            if check(now, word[i], j):
                temp = add(now, word[i], j)
                # 如果连接后的字符串与当前字符串相同,则跳过 包含了
                if temp == now:
                    continue
                used[i] += 1
                dfs(temp)
                used[i] -= 1


# 从起始单词开始递归搜索
dfs(beginn)
# 输出最长字符串的长度
print(ans)

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/147972.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【吐血总结】前端开发:一文带你精通Vue.js前端框架(七)

文章目录 前言1️⃣事件处理器2️⃣表单3️⃣总结 前言 上一篇中我们学习了vue.js 的条件语句、循环语句等知识点.,现在让我们接着Vue系列的学习。 Vue中事件处理器、表单等在开发中的作用不可或缺,本文将基于实例进行以上知识点的讲解。 1️⃣事件处理器…

Oracle如何快速删除表中重复的数据

方法一: 在Oracle中,你可以使用DELETE语句结合ROWID和子查询来删除重复的记录。以下是一个示例: DELETE FROM your_table WHERE ROWID NOT IN (SELECT MAX(ROWID)FROM your_tableGROUP BY column1, column2, ... -- 列出用于判断重复的列 )…

6大赛题,超148万奖池!2023无锡国际人工智能算法大赛等你来挑战!

各位人工智能卓越的推动者们,我们诚邀您参与【2023年无锡国际人工智能算法大赛】,探索未来AI创新的巅峰之战! 比赛为您提供与全球AI开发者技术切磋的机会,不仅是一场竞技,更是智慧的盛宴。 本次大赛总奖金超过148万&…

【FPGA】zynq 单端口RAM 双端口RAM 读写冲突 写写冲突

RAMRAM读写分类RAM原理及实现RAM三种读写模式不变模式写优先读优先 单端口 RAM伪双端口 RAM真双端口 RAM读写冲突和写写冲突读写冲突写写冲突总结: RAM RAM 的英文全称是 Random Access Memory,即随机存取存储器,简称随机存储器,…

什么是OpenCL?

什么是OpenCL? 1.概述 OpenCL(Open Computing Language 开放计算语言)是一种开放的、免版税的标准,用于超级计算机、云服务器、个人计算机、移动设备和嵌入式平台中各种加速器的跨平台并行编程。OpenCL是由Khronos Group创建和管理的。OpenCL使应用程序…

requests库验证错误解决方法

用户在使用requests库进行http请求时,遇到了一个AuthenticationRequired(身份验证必须)的错误。但是,当使用urllib.request.urlopen进行相同的操作时,却能够成功。同时,用户提供了自己的系统信息&#xff0…

记一次线上问题引发的对 Mysql 锁机制分析 | 京东物流技术团队

背景 最近双十一开门红期间组内出现了一次因 Mysql 死锁导致的线上问题,当时从监控可以看到数据库活跃连接数飙升,导致应用层数据库连接池被打满,后续所有请求都因获取不到连接而失败 整体业务代码精简逻辑如下: Transaction p…

requests Python 官方文档中的 py3 请求链接问题及解决方案

作为一位程序员,加班对我来说并不陌生。虽然老板常说加班是对挑战的追求,但我更愿意将其看作是与bug约会的机会。在这篇文章中,我将分享一个我在requests Python 官方文档中遇到的问题,并给出解决方案。问题在于如何获取py3的请求…

锐捷 Smartweb管理系统命令注入漏洞复现 [附POC]

文章目录 锐捷 Smartweb管理系统命令注入漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 锐捷 Smartweb管理系统命令注入漏洞复现 [附POC] 0x01 前言 免责声明:请勿利用文章内的相关技术从事非法测…

VMware 安装CentOS7

一、软件准备 VMware 虚拟机安装 官网下载链接:VMware pro 17 下载链接 下载 VMware Workstation Pro | CN vm安装教学就不在细说,纯傻瓜式安装 Centos 7镜像文件下载 下载地址: Index of /centos/ | 清华大学开源软件镜像站 | Tsinghua O…

AI+视觉,共话新能源企业数字化转型新可能

​ 近日,“新能源芯机遇2023新能源行业数字化赋能高峰论坛”在江苏常州隆重召开。本次论坛由常州市人民政府、中国能源研究会指导,武进区人民政府、常州市工业和信息化局、英特尔(中国)有限公司、阿里云计算有限公司共同举办&…

Android实验:Activity界面基础

目录 前言实验目的实验内容实验要求代码实现mainActivityResultActivityactivity_mainactivity_result 结果展示 前言 我们都知道,activity是Android中最重要的组件之一,关于activity的具体内容在这里就不多赘述,主打的就是一个主次分明&…

【C++】哈希(模拟实现unordered系列容器)

一、哈希表的改造 1、模板参数列表的改造 K:关键码类型V:不同容器V的类型不同。如果是 unordered_map,V 代表一个键值对;如果是 unordered_set,V 为 K。KeyOfValue:因为 V 的类型不同,通过 valu…

京东API商品详情接口丨关键词搜索接口丨优惠券接口丨京东店铺所有商品接口

京东API商品详情接口,关键词搜索接口,优惠券接口,京东店铺所有商品接口如下: item_get-获得JD商品详情 公共参数 请求地址: https://o0b.cn/anzexi 名称类型必须描述keyString是调用key(必须以GET方式拼接在URL中&…

相关关系与因果关系

本文来自:https://towardsdatascience.com/a-step-by-step-guide-in-detecting-causal-relationships-using-bayesian-structure-learning-in-python-c20c6b31cee5 作者:Erdogan Taskesen 在机器学任务中,确定变量间的因果关系(c…

BUUCTF 荷兰宽带数据泄露 1

BUUCTF:https://buuoj.cn/challenges 题目描述: 下载附件,解压得到一个.bin文件。 密文: 解题思路: 1、刚开始没什么思路,看了别人的题解,了解到一个新工具RouterPassView。大多数现代路由器都可以让您备…

遍历一个对象,并得出所对应的

var dates {//定义的对象year:now.getFullYear(),month:now.getMonth()1,date:now.getDate(),hour:now.getHours(),minute:now.getMinutes(),second:now.getSeconds() }//开始遍历循环 var val; for (val in dates){console.log(对象名称:val-对象的值:…

PDF文件标题修改方法

目录 一、PDF文件的标题和名称 二、标题修改方法 1.浏览器打开PDF Editor Free网站 2.点击Free Oline 3.选择第三个从本地上传PDF附件 4.将附件上传,两种方法都可以​编辑 5.等待加载,附件大的情况下会有些慢,耐心等待即可 6. 导入文…

MATLAB中uiwait函数用法

目录 语法 说明 示例 等待对警报对话框的响应 等待对模态消息对话框的响应 等待按钮按下 等待超时 uiwait函数功能是阻止程序执行并等待恢复。 语法 uiwait uiwait(f) uiwait(f,timeout) 说明 uiwait 阻止程序执行,直至调用了 uiresume 函数或删除了当前…

Linux_包管理_apt相关命令的使用

以思维导图的形式整理了下apt相关的命令,便于查阅,主要分为软件源、安装卸载升级、查看; 1、软件源 2、安装、卸载、升级 3、查看 参考链接: Using apt Commands in Linux [Ultimate Guide] 6. apt更新软件源 — 快速使用手册—…