形成给定字符串所需的最小前缀和后缀的数量

冬婷同学_2799

冬婷同学_2799

2023-08-30

1701人浏览

转载

形成给定字符串所需的最小前缀和后缀的数量

前缀是给定字符串中的子字符串,从第零个索引开始,长度可达字符串的大小。同样,后缀是任意长度为 1 到字符串大小的子字符串,并以最后一个索引结束。我们将得到两个字符串,并且必须以任何方式使用第二个字符串的任意数量的前缀和后缀来创建第一个字符串。如果无法从给定方法创建给定字符串,那么我们将返回 -1。

示例

Input 1: string str1 = “tutorialspoint”  string str2 = “pointstutorial”
Output:  2

Explanation

的中文翻译为:

解释

我们可以使用前缀“points”和后缀“tutorial”,通过将它们连接起来,我们可以得到第一个字符串。这只需要两个子字符串,这就是我们的答案或输出。

Input 2: string str1 = “randomstring” string str2 = “anotherstring” 
Output: -1

Explanation

的中文翻译为:

解释

我们无法从给定的第二个字符串的后缀或前缀中获取第一个字符串。

方法

为了解决这个问题,我们将使用动态规划的概念,即通过存储已经发生的实例来解决。

  • 首先,我们将创建一个函数,该函数将以两个字符串作为参数,并返回一个整数。

  • 在该函数中,首先我们将获取字符串的长度,并创建一个哈希集和一个临时字符串来获取前缀。

  • 我们将遍历第二个字符串,并获取所有的前缀,并将它们存储在哈希集中。同样地,通过从后向前遍历字符串,我们可以获取所有的后缀,并将它们存储在哈希集中。

    LangGPT
    LangGPT

    LangGPT是一款AI提示词工具,什么 LangGPT是一种...。

    下载
  • 然后我们将创建一个数组来存储动态规划的结果,并在数组的每个索引位置存储-1。

  • 使用嵌套的 for 循环,我们将第一个字符串分成块,并查找是否可以连接哈希映射中的所有块。

  • 我们将尽力减少所需的子字符串数量,如果不可能,将返回-1。

示例

#include <bits>
using namespace std;
// function to find the required number of substrings
int count(string str1, string str2){
   unordered_set<string> st; // set to store the strings from the prefix and suffix 
   string temp = "";// string to store the prefixes and suffixes 
   int len1 = str1.size(); // size of the first string 
   int len2 = str2.size(); // getting size of the second 
   
   // getting prefixes of string second 
   for (int i = 0; i = 0; i--){
      temp = str2.substr(i); // getting suffixes		
      st.insert(temp); // adding suffixes to the set 
   }
   // Initialize memo array to store the answer
   int memo[len1+1];
   memset(memo, -1, sizeof(memo)); // initializing array 
   memo[0] = 0; 
   
   // applying the concepts of dp 
   // traversing over the main string and will try to 
   // partition string into chunks 
	for (int i = 0; i <h3>输出</h3>
<pre class="brush:php;toolbar:false;">The minimum count of prefixes and suffixes of a string required to form given string is 2

时间和空间复杂度

上述代码的时间复杂度为 O(N^2),因为我们获取的所有后缀的复杂度都很高,但可以通过反转字符串来降低时间复杂度。此外,我们将字符串存储到哈希集中使得时间复杂度很高,并且嵌套 for 循环以进行动态编程。

上述代码的空间复杂度为 O(N^2),因为我们将所有后缀和前缀存储在哈希图中。

结论

在本教程中,我们实现了一段代码来找到给定字符串的后缀和前缀中最小的子字符串数量,以创建另一个给定字符串,如果不可能,我们打印-1。我们使用了动态规划的概念,通过将元素存储在哈希集中,然后使用时间和空间复杂度为O(N^2)的嵌套循环。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

120

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

60

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

2026.11.05

100

12

DBeaver安全防护教程大全
DBeaver安全防护教程大全

DBeaver安全防护专题,围绕数据库连接安全、账号密码保护和访问权限管理展开,整理SSL/TLS加密连接、SSH隧道、数据库凭据保存及证书验证等配置方法,同时介绍敏感信息保护、远程连接风险和高权限账号使用等注意事项,帮助用户提高数据库日常管理的安全性。

2026.11.05

100

12

DBeaver连接创建与配置教程
DBeaver连接创建与配置教程

本专题聚焦DBeaver数据库连接配置与管理,覆盖从新建连接、选择数据库类型到填写连接参数和验证连接的完整流程。针对MySQL、PostgreSQL、SQL Server等常见数据库,整理相应的连接设置方法,并提供驱动缺失、认证失败和连接异常等问题的排查方向。

2026.11.04

100

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
PHP基础入门课程
PHP基础入门课程

共33课时 | 3.5万人学习

Go语言教程-全程干货无废话
Go语言教程-全程干货无废话

共100课时 | 18.2万人学习

走进 ES6 新标准语法
走进 ES6 新标准语法

共15课时 | 2万人学习