旋转字符串 | 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; // 返回前缀函数数组}
}

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

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

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

c# 排序、强转枚举

List<Tuple<double,int>> mm中doble从小到大排序 mm本身排序 在C#中&#xff0c;如果你有一个List<Tuple<double, int>>类型的集合mm&#xff0c;并且你想要根据Tuple中的double值&#xff08;即第一个元素&#xff09;从小到大进行排序&#xff0c;同…

[Qt][对话框][下]详细讲解

目录 1.Qt内置对话框0.有哪些1.消息对话框 QMessageBox2.颜色对话框 QColorDialog3.⽂件对话框 QFileDialog4.字体对话框 QFontDialog5.输⼊对话框 QInputDialog6.进度条对话框 QProgressDialog 1.Qt内置对话框 0.有哪些 Qt提供了多种可复⽤的对话框类型&#xff0c;即Qt标准…

【启明智显技术分享】工业级HMI芯片Model3C/Model3A开发过程中问题记录笔记二

一、Model3C/Model3A芯片介绍 Model3C/Model3A是启明智显针对工业、行业以及车载产品市场推出的一款高性能、低成本的工业级HMI&#xff08;Human-Machine Interface&#xff0c;人机界面&#xff09;芯片。两颗芯片硬件PIN TO PIN&#xff1b;区别在于内置的PSRAM大小不同。该…

百度地图动态绘制台风轨迹

效果图如下: 台风测试数据获取 关键代码: /*** 动态绘制点和线*/drawMakerByAnimate () {const pointsMap = typhoneData.points;const title = typhoneData.tfid + typhoneData.name;if (!pointsMap || pointsMap.length === 0) {return;}if (this.markers.length > 0 &…

Godot《躲避小兵》实战之设置项目

通过之前的学习我们已经基本了解了godot的界面&#xff0c;知道如何创建项目以及节点。那么&#xff0c;从这一章节我们将进入godot官方给我们提供的一个2D游戏开发的小教程进行入手&#xff0c;这个游戏并不是我自己的作品&#xff0c;而是我通过学习完之后&#xff0c;对其进…

C#如何将自己封装的nuget包引入到项目中

问题 自己封装好了一个nuget包&#xff0c;但是不想上传到外网&#xff0c;想局域网使用&#xff0c;有两种方案 搭建私有nuget仓库放到离线文件夹中直接使用 第一种方式请请参考proget安装 下面主要是第二种方式 准备 新建类库项目 using System;namespace ClassLibrary…

数据结构--图(Graph)

定义 图&#xff08;Graph&#xff09;是由顶点的有穷非空集合和顶点之间边的集合组成的一种非线性表结构&#xff0c;通常表示为&#xff1a;G(V,E)&#xff0c;其中&#xff0c;G表示一个图&#xff0c;V是图G中顶点的集合&#xff0c;E是图G中边的集合。 顶点&#xff08;…

阿里云智能大数据演进

本文根据7月24日飞天发布时刻产品发布会、7月5日DataFunCon2024北京站&#xff1a;大数据大模型.双核时代实录整理而成&#xff0c;演讲信息如下&#xff1a; 演讲人&#xff1a;徐晟 阿里云研究员/计算平台产品负责人 主要内容&#xff1a; Overview - 阿里云大数据 AI 产品…

经典算法题总结:数组常用技巧(双指针,二分查找和位运算)篇

双指针 在处理数组和链表相关问题时&#xff0c;双指针技巧是经常用到的&#xff0c;双指针技巧主要分为两类&#xff1a;左右指针和快慢指针。所谓左右指针&#xff0c;就是两个指针相向而行或者相背而行&#xff1b;而所谓快慢指针&#xff0c;就是两个指针同向而行&#xf…

【YOLO5 项目实战】(3)PCB 缺陷检测

欢迎关注『youcans动手学模型』系列 本专栏内容和资源同步到 GitHub/youcans 【YOLO5 项目实战】(1)YOLO5 环境配置与测试 【YOLO5 项目实战】(2)使用自己的数据集训练目标检测模型 【YOLO5 项目实战】(3)PCB 缺陷检测 【YOLO5 项目实战】(3)PCB 缺陷检测 1. PCB 缺陷检…

vue-cli 中 配置 productionSourceMap 为 false 失效?

背景 最近 发现 vuecli 构建的 项目中配置的 productionSourceMap 为 false 后 &#xff0c;生产代码 还是能够看到 sourceMap 文件 。 原因 生效前提条件 得设置 NODE_ENV 为 production 才会生效&#xff01; 解决 直接修改生产环境的配置 NODE_ENV 为 production 直接覆…

融资3亿美元——月之暗面:AI大模型领域的新星

月之暗面&#xff0c;这个名字在AI领域引起了不小的震动。作为国内大模型创业企业的佼佼者&#xff0c;月之暗面以其独特的技术优势和商业模式&#xff0c;迅速在激烈的市场竞争中崭露头角。同时以其出色的长文本处理能力和创新的商业模式吸引了众多投资者的目光。 优牛企讯-企…

基于DETR模型实现交通标志检测

交通标志检测在自动驾驶和交通监控中是一个重要的问题。目标检测技术极大地促进了这一过程的自动化。本文实现基于DETR目标检测模型识别交通标志。 Tiny LISA交通标志检测数据集 本文数据集使用Kaggle上提供的Tiny LISA交通标志检测数据集(https://www.kaggle.com/datasets/mm…

手把手教你CNVD漏洞挖掘 + 资产收集

0x1 前言 挖掘CNVD漏洞有时候其实比一般的edusrc还好挖&#xff0c;但是一般要挖证书的话&#xff0c;还是需要花时间的&#xff0c;其中信息收集&#xff0c;公司资产确定等操作需要花费一定时间的。下面就记录下我之前跟一个师傅学习的一个垂直越权成功的CNVD漏洞通杀&#…

MySql 5.7.1 分区的实践

在性能优化中&#xff0c;Mysql 进行分区&#xff0c;能有效提高查询效率&#xff0c;因此开始百度了起来。但是结果总不是那么一番风顺的。如今使用 uuid 作为主键的情况已是主流&#xff0c;因此在给表增加分区时&#xff0c;出现了如下错误&#xff1a; 错误&#xff1a; A …

AI在医学领域:联邦学习 (FL) 在肿瘤学的应用综述

关键词&#xff1a;联邦学习 (Federated Learning, FL)、机器学习 (Machine Learning, ML)、肿瘤学 (Oncology)、数据隐私 (Data Privacy)、精准医疗 (Precision Medicine)、多模态 (Multi-modal) 肿瘤学正在经历快速的变革&#xff0c;这得益于机器学习&#xff08;ML&#xf…

奥德彪视频素材去哪里找?视频素材网站分享

今天我们来聊一聊一个非常实用的话题——视频素材网站推荐&#xff0c;尤其是奥德彪视频素材。这个名词可能对你来说有些陌生&#xff0c;但别担心&#xff0c;跟着我一起探索&#xff0c;你会发现这是一个充满创意与乐趣的旅程。 蛙学网 首先要介绍的是蛙学网。这是一个视频素…

【传知代码】医疗AI:轻量级图像分割新突破(论文复现)

在医学图像领域&#xff0c;精准的图像分割技术一直是提高诊断效率和准确性的关键&#xff0c;然而传统的图像分割方法常常受到计算资源和处理速度的限制&#xff0c;尤其在资源紧张的医疗环境中更是如此。随着人工智能技术的飞速发展&#xff0c;我们迎来了一个激动人心的新时…

PAT--1101.B是A的多少倍

题目描述 算法分析 把数字转为字符串处理&#xff0c;会简化问题 完整代码 #include<bits/stdc.h> //万能头文件 //#include<iostream> //#include<string> //#include <iomanip> // 包含 std::fixed 和 std::setprecision using namespace std;…

PHP汽车保养维修信息管理系统小程序源码

&#x1f697;爱车守护神器&#xff01;揭秘“汽车保养维修信息管理系统”全攻略&#x1f50d; &#x1f525;【开篇揭秘&#xff1a;为何你需要它&#xff1f;】&#x1f525; 在这个快节奏的时代&#xff0c;爱车不仅是代步工具&#xff0c;更是生活品质的象征。但你是否曾…