(字符串 ) 459. 重复的子字符串——【Leetcode每日一题】

news/2024/2/29 3:24:43

❓459. 重复的子字符串

难度:简单

给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

示例 2:

输入: s = “aba”
输出: false

示例 3:

输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

提示

  • 1 < = s . l e n g t h < = 1 0 4 1 <= s.length <= 10^4 1<=s.length<=104
  • s 由小写英文字母组成

💡思路:

法一:暴力

  • 就是一个 for 循环获取 子串的终止位置, 然后判断子串是否能重复构成字符串,又嵌套一个 for循环,所以是 O ( n 2 ) O(n^2) O(n2) 的时间复杂度。

法二: KMP(后续更新)

🍁代码:(Java、C++)

法一:暴力

Java

class Solution {public boolean repeatedSubstringPattern(String s) {int n = s.length();for(int i = 1; i <= n / 2; i++){if(n % i != 0) continue;for(int j = 0; j <= n - 2 * i; j += i){String str1 = s.substring(j, j + i);String str2 = s.substring(j + i, j + 2 * i);if(str1.compareTo(str2) != 0) break;if(j == n - 2 * i) return true;}}return false;}
}

C++

class Solution {
public:bool repeatedSubstringPattern(string s) {int n = s.size();for(int i = 1; i <= n / 2; i++){if(n % i != 0) continue;for(int j = 0; j <= n - 2 * i; j += i){if(s.compare(j, i, s, j + i, i) != 0) break;if(j == n - 2 * i) return true;}}return false;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),其中 n 为字符串 s 的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


https://www.jiucaihua.cn/news/show-4626973.html

相关文章

【Proteus仿真】【51单片机】出租车计价器

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真51单片机控制器&#xff0c;使用LCD1604显示模块、按键模块、蜂鸣器模块、DS1302时钟、速度检测模块、 直流电机驱动&#xff0c;票据打印等。 主要功能&#xff1a; 系统运行后&a…

数据库之主键、联合主键

参考文章&#xff1a;数据库之主键、联合主键 一、主键、联合主键简介 数据库主键是用来标记数据记录唯一性的列&#xff0c;不能为空&#xff0c;不能重复。 主键具有的特点&#xff1a;唯一性、非空性。 数据库联合主键&#xff1a;可以将多个列同时作为主键。&#xff0…

笔试强训 Day 7

选择题&#xff1a; 1.在&#xff08;&#xff09;情况下适宜采用 inline 定义内联函数 A 函数体含有循环语句 B 函数体含有递归语句C 函数代码少、频繁调用 D 函数代码多&#xff0c;不常调用 复习一下内联函数 在编译阶段&#xff0c;会将内联函数展开 —— 将函数调用替换成…

基于深度学习的高精度推土机检测识别系统(PyTorch+Pyside6+YOLOv5模型)

摘要&#xff1a;基于深度学习的高精度推土机检测识别系统可用于日常生活中检测与定位推土机目标&#xff0c;利用深度学习算法可实现图片、视频、摄像头等方式的推土机目标检测识别&#xff0c;另外支持结果可视化与图片或视频检测结果的导出。本系统采用YOLOv5目标检测模型训…

【react全家桶】react-Hook (下)

本人大二学生一枚&#xff0c;热爱前端&#xff0c;欢迎来交流学习哦&#xff0c;一起来学习吧。 <专栏推荐> &#x1f525;&#xff1a;js专栏 &#x1f525;&#xff1a;vue专栏 &#x1f525;&#xff1a;react专栏 文章目录 15【react-Hook &#xff08;下&#x…

深度学习论文分享(三)Look More but Care Less in Video Recognition(NIPS2022)

深度学习论文分享&#xff08;三&#xff09;Look More but Care Less in Video Recognition&#xff08;NIPS2022&#xff09; 前言Abstract1. Introduction2 Related Work2.1 Video Recognition2.2 Redundancy in Data&#xff08;数据冗余&#xff09; 3 Methodology3.1 Arc…

【018】C++的指针数组和数组指针

C 指针数组和数组指针 引言一、指针数组1.1、数值的指针数组1.2、字符的指针数组1.3、二维字符数组 二、指针的指针三、数组指针3.1、数组首元素地址和数组首地址3.2、数组指针的使用示例3.3、二维数组和数组指针的关系 四、多维数组的物理存储总结 引言 &#x1f4a1; 作者简介…

VTK 开发中遇到问题整理

1 Generic Warning VTK 开发 中是到 vtkOutputWindow 弹窗并提示Generic Warning&#xff1a;… vtkOutputWindow 弹窗 解决方法&#xff1a; 添加&#xff1a; #include <vtkOutputWindow.h> 在 main.cpp函数中添加&#xff1a; vtkOutputWindow::SetGlobalWarningD…

四、若依(前后端分离)项目构建docker 镜像

若依(前后端分离&#xff09;项目构建docker 镜像 1. 构建好ruoyi-admin.jar包&#xff0c;上传到服务器项目目录下 2. 创建conf目录将若依项目&#xff08;Spring boot &#xff09;配置文件修改好&#xff0c;上传存入conf目录 注意&#xff1a;这里的地址不能写127.0.0.1和…

Rust每日一练(Leetday0013) 解数独、外观数列、组合总和

目录 37. 解数独 Sudoku Solver &#x1f31f;&#x1f31f;&#x1f31f; 38. 外观数列 Count and Say &#x1f31f;&#x1f31f; 39. 组合总和 Combination Sum &#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Rust每日一练 专栏 Gola…