讲师中心 微信公众号

工具推荐

视频效率加速
Seko
Seko

AI短剧一键生成成片

立刻MV
立刻MV

低成本歌曲 MV、视频生成

剧云
剧云

中文短剧剧本制作平台

updream

一键生成高质量推广成片

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

冬婷同学_2799

冬婷同学_2799

发布时间:2023-08-30 22:37:06

|

1701人浏览过

|

来源于tutorialspoint

转载

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

前缀是给定字符串中的子字符串,从第零个索引开始,长度可达字符串的大小。同样,后缀是任意长度为 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

的中文翻译为:

解释

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

方法

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

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

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

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

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

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

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

示例

#include <bits/stdc++.h>
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 < len2; i++){
      temp += str2[i]; // adding the characters to temporary string
      st.insert(temp); // insert current string to set 
   }
   
   // getting all the sufixes 
   for (int i = len2-1; 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 < len1; i++){
      for (int j = 1; j <= len1 - i; j++){
		   // check if the set contain current substring 
         if (st.find(str1.substr(i, j)) != st.end()){
            if (memo[i] == -1){
               continue;
            }
            if (memo[i + j] == -1){
               memo[i + j] = memo[i] + 1;
            }
            else {
               memo[i + j] = min(memo[i + j], memo[i] + 1);
            }
         }
      }
   }
   // Return the answer
   return memo[len1];
}
int main(){
   string str1 = "tutorialpoints";
   string str2 = "pointstutorial";
   // calling function to find the minimum number of substrings required
   cout <<"The minimum count of prefixes and suffixes of a string required to form given string is "<<count(str1, str2)<<endl;
   return 0;
}

输出

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)的嵌套循环。

热门AI工具

更多
SoundView
SoundView Hot

SoundView是一款面向跨境电商的视频翻译、配音和本地化 AI 创作平台。

Atoms
Atoms Hot

Atoms是一款AI智能体工具,第一支自动构建真实业务的 AI 团队。

切问学术

切问学术是一款AI论文写作工具,复旦大学NLP团队推出的AI学术智能体。

UpDream
UpDream Hot

一款AI视频创作工具,主要用于哔哩哔哩推出的自研AI视频创作工具,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

PixTV
PixTV Hot

PixTV是一款面向AIGC内容创作的AI视频生成工具。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

蛙蛙写作

一款AI论文写作工具,主要用于超级AI智能写作助手,适合需要提升相关任务效率的用户。

相关专题

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

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

140

2026.11.12

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

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

100

2026.11.12

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

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

80

2026.11.12

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

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

160

2026.11.06

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

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

140

2026.11.06

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

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

120

2026.11.06

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

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

100

2026.11.05

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

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

100

2026.11.05

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

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

100

2026.11.04

热门下载

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

精品课程

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

共33课时 | 3.5万人学习

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

共100课时 | 18.2万人学习

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

共15课时 | 2万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn