当前位置: 首页 > news >正文

旋转字符串 | LeetCode-796 | 模拟 | KMP | 字符串匹配

🙋大家好!我是毛毛张!
🌈个人首页: 神马都会亿点点的毛毛张
🕹️KMP算法练习题

LeetCode链接:796. 旋转字符串

文章目录

  • 1.题目描述🍑
  • 2.题解🫐
    • 2.1 暴力解法🫒
    • 2.2 模拟🥭
    • 2.3 字符串匹配 - 移动匹配🥑
      • 2.3.1 内置函数🥥
      • 2.3.2 KMP🍊

1.题目描述🍑

给定两个字符串, sgoal。如果在若干次旋转操作之后,s 能变成 goal ,那么返回 true

s旋转操作 就是将 s 最左边的字符移动到最右边。

  • 例如, 若 s = 'abcde',在旋转一次之后结果就是'bcdea'

示例 1:

输入: s = "abcde", goal = "cdeab"
输出: true

示例 2:

输入: s = "abcde", goal = "abced"
输出: false

提示:

  • 1 <= s.length, goal.length <= 100
  • sgoal 由小写英文字母组成

2.题解🫐

2.1 暴力解法🫒

class Solution {public boolean rotateString(String s, String goal) {// 检查两个字符串的长度,如果长度不同,返回 falseif (s.length() != goal.length()) return false;char[] chs = s.toCharArray();// 将字符串 s 转换为字符数组char[] cht = goal.toCharArray();// 将目标字符串 goal 转换为字符数组// 遍历每一个可能的旋转位置for (int i = 0; i < chs.length; i++) {// 保存当前字符,以便进行旋转char temp = chs[0];// 将字符数组向左旋转一位for (int j = 0; j < cht.length - 1; j++) {chs[j] = chs[j + 1];}// 将保存的字符放到数组末尾chs[chs.length - 1] = temp;// 如果当前旋转后的字符数组等于目标字符数组,返回 trueif (Arrays.equals(chs, cht)) return true;}return false;// 如果没有找到任何匹配,返回 false}
}

2.2 模拟🥭

  • 上面我们是通过将字符串转换成字符数组,然后实际进行旋转,当时实际上并不需要,我们可以通过取模的方式来模拟旋转字符串,这种方法称为模拟
  • 首先,如果 s s s g o a l goal goal的长度不一样,那么无论怎么旋转, s s s都不能得到 g o a l goal goal,返回 f a l s e false false。在长度一样(都为 n)的前提下,假设 s s s旋转 i i i位,则与 g o a l goal goal中的某一位字符$ goal[j] 对应的原 对应的原 对应的原s$中的字符应该为 s [ ( i + j ) m o d n ] s[(i+j)\ mod\ n] s[(i+j) mod n]。在固定 i i i的情况下,遍历所有 j j j,若对应字符都相同,则返回 t r u e true true。否则,继续遍历其他候选的 i i i。若所有的 i i i都不能使 s s s变成 g o a l goal goal,则返回 f a l s e false false
class Solution {public boolean rotateString(String s, String goal) {// 检查两个字符串的长度,如果不相等则返回 falseif (s.length() != goal.length()) return false;int len = s.length(); // 获取字符串 s 的长度// 遍历字符串 s 的每一个字符作为旋转的起始位置for (int i = 0; i < len; i++) {int j; // 初始化目标字符串 goal 的索引// 遍历目标字符串 goalfor (j = 0; j < len; j++) {// 通过模运算计算旋转后的字符在字符串 s 中的位置,并进行比较if (s.charAt((i + j) % len) != goal.charAt(j)) break; // 如果不匹配,跳出内层循环}// 如果 j 达到目标字符串的长度,表示完全匹配,返回 trueif (j == len) return true;}// 如果没有找到匹配,返回 falsereturn false;}
}

2.3 字符串匹配 - 移动匹配🥑

  • 首先,如果 sgoal 的长度不一样,那么无论怎么旋转,s 都不能得到 goal,返回 false。字符串 s+s 包含了所有 s 可以通过旋转操作得到的字符串,只需要检查 goal 是否为 s+s 的子字符串即可。

2.3.1 内置函数🥥

class Solution {public boolean rotateString(String s, String goal) {return s.length() == goal.length() && (s+s).contains(goal);}
}

2.3.2 KMP🍊

class Solution {public boolean rotateString(String s, String goal) {// 检查字符串的长度,如果不相等则返回 falseif (s.length() != goal.length()) return false;// 将字符串 s 进行拼接,以便于处理旋转情况s = s + s;// 生成目标字符串 goal 的前缀函数数组int[] next = getNext(goal); int j = 0; // 匹配指针,用于遍历目标字符串 goal// 遍历拼接后的字符串 sfor (int i = 0; i < s.length(); i++) {// 当前字符不匹配时,根据前缀函数回退 jwhile (j > 0 && s.charAt(i) != goal.charAt(j)) j = next[j - 1];if (s.charAt(i) == goal.charAt(j)) j++;// 如果字符匹配,增加 j// 如果 j 达到目标字符串的长度,表示完全匹配,返回 trueif (j == goal.length()) return true;}// 如果没有找到匹配,返回 falsereturn false;}// 生成目标字符串的前缀函数数组public int[] getNext(String s) {int n = s.length();int[] next = new int[n]; // 存储前缀函数的数组int j = 0; // 前缀指针next[0] = 0; // 第一个字符的前缀长度为0// 遍历字符串,生成前缀函数数组for (int i = 1; i < n; i++) {// 当前字符不匹配时,回退前缀指针 jwhile (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];if (s.charAt(i) == s.charAt(j)) j++;// 如果字符匹配,前缀长度增加next[i] = j;// 记录前缀长度到 next 数组}return next; // 返回前缀函数数组}
}

都看到这了,不妨一键三连再走吧!

🌈欢迎和毛毛张一起探讨和交流!
联系方式参见个人主页:
神马都会亿点点的毛毛张

相关文章:

旋转字符串 | LeetCode-796 | 模拟 | KMP | 字符串匹配

&#x1f64b;大家好&#xff01;我是毛毛张! &#x1f308;个人首页&#xff1a; 神马都会亿点点的毛毛张 &#x1f579;️KMP算法练习题 LeetCode链接&#xff1a;796. 旋转字符串 文章目录 1.题目描述&#x1f351;2.题解&#x1fad0;2.1 暴力解法&#x1fad2;2.2 模拟…...

网络安全测试工具Burp Suite基本使用

一、介绍 Burp Suite 是一款由 PortSwigger 开发的集成网络安全测试工具&#xff0c;广泛用于渗透测试和漏洞扫描。它提供了一系列功能强大的工具和功能&#xff0c;帮助安全研究人员和渗透测试人员识别和修复 Web 应用程序中的安全漏洞。以下是 Burp Suite 的主要功能和特点&…...

使用pytest+selenium编写网页UI自动化脚本和用例

1 UI自动化测试 UI自动化测试&#xff08;User Interface Automation Testing&#xff09;是一种通过编写脚本或使用自动化测试工具&#xff0c;对界面&#xff08;UI&#xff09;进行自动化测试的方法。原理主要是模拟用户打开客户端或网页的UI界面&#xff0c;自动化执行用户…...

新能源遇“秋老虎”,8月第二周销量集体下滑,问界惨遭腰斩

文/王俣祺 导语&#xff1a;随着日前7月份乘用车销量的公布&#xff0c;我们发现7月并没有因6月各车企的“冲量”行为迎来反噬&#xff0c;对于这种“淡季不淡”的现象市场上一片看好。但从近日公布的8月销量数据来看&#xff0c;人们对于“秋老虎”的恐怖可以说是一无所知。随…...

SEO模板网站的wordpress主题最适合google外贸SEO

在寻找最适合Google外贸SEO的WordPress主题时&#xff0c;有几个关键因素需要考虑&#xff1a;速度、SEO友好性、多语言支持、以及是否易于定制。以下是一些推荐的WordPress主题&#xff0c;它们不仅速度快&#xff0c;而且对SEO非常友好&#xff0c;非常适合外贸网站&#xff…...

fetch跨域请求数据的前端设置和后端php的header设置

跨源请求&#xff0c;也称为CORS&#xff08;Cross-Origin Resource Sharing&#xff09;请求&#xff0c;是Web开发中常见的一种需求&#xff0c;允许一个网页的JavaScript代码向与该网页不同源的服务器发出HTTP请求。以下是使用JavaScript中的fetch函数进行跨源请求的一个基本…...

Ted靶机

信息收集&#xff1a; 靶机地址&#xff1a;https://www.vulnhub.com/entry/ted-1,327/ &#xff08;1&#xff09;ip扫描 nmap 192.168.254.0/24 -sn | grep -B 2 00:0C:29:FF:7F:9A &#xff08;2&#xff09;端口扫描 nmap -p- -A 192.168.254.159 &#xff08;3&#x…...

HarmonyOS ArkTS 构建布局

在 HarmonyOS 中&#xff0c;ArkTS 是一种基于 TypeScript 的编程语言&#xff0c;专为开发 HarmonyOS 应用而设计。构建布局是开发应用的关键步骤之一。以下是如何在 ArkTS 中构建布局的基本指南。 1. 创建项目和页面 首先&#xff0c;确保已经创建了一个 HarmonyOS 项目。如…...

yolov5详解(二):通过yaml文件构建完整模型

依然拿yolov5l v6.0版本来讲解 1. yaml文件 以下是yolov5l.yaml文件内容 # YOLOv5 &#x1f680; by Ultralytics, GPL-3.0 license# Parameters nc: 80 # number of classes depth_multiple: 1.0 # model depth multiple width_multiple: 1.0 # layer channel multiple …...

8月8日学习笔记 python基础

1.环境 python2&#xff0c; python3 yum list installed|grep python yum -y install python3 # 最新安装3.12可以使⽤源码安装&#xff0c;教程是在第⼀个星期pdf python3 --version 3.6.8 #进⼊到python的编辑状态 python3 # 如果直接输⼊python&#xff0c;也会进⼊到pyth…...

电动自行车出海黑马Avento独立站拆解(上)丨出海笔记

这次我们来拆解一个电动自行车的独立站 为什么选电动自行车&#xff1f; 因为全球疫情&#xff0c;带来出行问题——避免聚集&#xff0c;大家都减少了公共交通工具&#xff0c;而改为自行车&#xff0c;电动自行车...... 君不见疫情之后无论是出行自行车&#xff0c;还是健…...

Gerrit 使用教程

一、Gerrit简介 Gerrit&#xff0c;一种开放源代码的代码审查软件&#xff0c;使用网页界面。利用网页浏览器&#xff0c;同一个团队的程序员&#xff0c;可以相互审阅彼此修改后的代码&#xff0c;决定是否能够提交&#xff0c;退回或是继续修改。它使用版本控制系统Git作为底…...

sudu提权命令账号安全控制(su命令)执行单个命令并返回原用户、执行多个命令并返回原用户、保持当前环境变量、配置文件/etc/sudoers

su命令 su 命令是 Linux 和 Unix 系统中用于切换用户身份的命令。它允许一个用户变成另一个用户并以该用户的权限运行命令或启动新的 shell 会话。 基本语法 su [选项] [用户名] 用途&#xff1a; su[选项][-][用户[arg]…] 将有效用户id和组id更改为user的id。 A merely-im…...

【线性代数】【二】2.7 矩阵的秩

文章目录 前言一、向量组的秩二、矩阵的秩三、矩阵的可逆性与秩总结 前言 在前面的内容中&#xff0c;我们已经陆陆续续地给出了秩的概念。本文可以看成是对以往概念与性质的总结&#xff0c;那专门针对秩进行分析。 一、向量组的秩 在笔记2.2中&#xff0c;我们学习了极大线…...

计算机网络部分基础知识

网络协议的意义 单台主机内部的设备之间需要发送和接收消息&#xff0c;那么和相隔很远的两台主机之间发送消息有什么区别呢&#xff1f;两台主机通过网络发送消息&#xff0c;相当于两个网卡设备之间进行通信&#xff0c;最大的区别在于距离变长了。而距离变长带来的结果就是&…...

WESWOO合作的出海企业(一)

分享一些我们在shopify开发上合作的品牌介绍1. **韶音科技&#xff08;SHOKZ&#xff09;**&#xff1a; - WESWOO为韶音科技设计了多个产品页面&#xff0c;如OPENFIT、OPENSWIMPRO等&#xff0c;这些页面展示了产品特点、滑动特效、比较功能等&#xff0c;并通过品牌VI统一&a…...

vue 项目中 使用vxe-grid 表格中给表格的表头设置特殊的格式 , 并且给指定的列文字设置颜色

项目场景&#xff1a; 相关背景&#xff1a; vue 项目中 使用vxe-grid 表格中给表格的表头设置特殊的格式&#xff0c;并为指定的列文字设置颜色 实现方案&#xff1a; 具体实现方法及步骤&#xff1a; 一、给表格的表头设置特殊的格式 实现方式一&#xff1a; :header-row-s…...

基于SpringBoot的企业资产管理系统

TOC springboot117基于SpringBoot的企业资产管理系统 系统概述 1.1 研究背景 智慧养老是面向居家老人、社区及养老机构的传感网系统与信息平台&#xff0c;并在此基础上提供实时、快捷、高效、低成本的&#xff0c;物联化、互联化、智能化的养老服务。 随着科技进步&#…...

ps快捷键,学习

ps快捷键图片变的特别大&#xff0c;归位&#xff0c;ctrl0背景图层锁住 选中图层&#xff0c;点击顶部图层&#xff0c;新建&#xff0c;背景图层&#xff0c;确定&#xff0c;就解开了&#xff0c;想在锁住&#xff0c;在点一次...

python代码模拟服务器实验2:IO多路复用select

实验代码的环境是在windows&#xff0c;和linux是有差别的 在Windows系统上&#xff0c;select模块需要传递特定的对象类型&#xff0c;而不是文件描述符。在Unix-like系统上&#xff0c;文件描述符是一个整数&#xff0c;而在Windows上&#xff0c;select期望得到的是socket对…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...