😀前言
在程序设计中，字符串处理问题屡见不鲜，其中“字符串左旋”是一种常见操作，今天我们一起来探讨一个经典的左旋转字符串题目，以及一种优雅的解决方案——三步翻转法。
🏠个人主页：尘觉主页
文章目录
- 🥰左旋转字符串
- 题目链接
- 💝题目描述
- 💞分析与思路
- 举例说明
- 💞代码实现
- 代码详解
- 复杂度分析
- 😄总结
🥰左旋转字符串
题目链接
牛客网
💝题目描述
题目要求将给定字符串 SSS 从第 KKK 个位置分割为两个子串并互换位置。例如：
- 输入：
S = "abcXYZdef"，K = 3 - 输出：
"XYZdefabc"
解题的关键在于实现有效的字符串左旋，即将字符串的前 KKK 个字符移到末尾，形成新的字符串。
💞分析与思路
左旋转字符串可以通过切分字符串并拼接两部分的方式实现，但这种方法可能会导致大量的内存复制。三步翻转法是一种更加高效的方式，仅需对字符数组进行三次局部翻转即可完成目标操作：
- 将前 KKK 个字符翻转。
- 将剩余字符翻转。
- 最后对整个字符串再翻转一次。
举例说明
以 S = "abcXYZdef"，K = 3 为例：
- 第一步：翻转前 3 个字符
abc，得到cbaXYZdef。 - 第二步：翻转后续字符
XYZdef，得到cbaZYXfed。 - 第三步：将整个字符串翻转，得到
XYZdefabc，即我们期望的结果。
💞代码实现
接下来，我们使用 Java 语言实现三步翻转法。此算法时间复杂度为 O(n)，仅需常数级的额外空间，因此在性能和空间占用上都表现优异。
public class Solution {
public String LeftRotateString(String str, int n) {
// 边界条件检查
if (str == null || n >= str.length()) {
return str;
}
// 转换为字符数组，方便操作
char[] chars = str.toCharArray();
// 第一步：翻转前 n 个字符
reverse(chars, 0, n - 1);
// 第二步：翻转后面的字符
reverse(chars, n, chars.length - 1);
// 第三步：将整个字符串翻转
reverse(chars, 0, chars.length - 1);
return new String(chars);
}
// 辅助函数：翻转指定区间的字符
private void reverse(char[] chars, int i, int j) {
while (i < j) {
swap(chars, i++, j--);
}
}
// 辅助函数：交换字符数组的两个元素
private void swap(char[] chars, int i, int j) {
char t = chars[i];
chars[i] = chars[j];
chars[j] = t;
}
}
代码详解
- reverse函数：负责翻转字符数组中某个指定区间的字符。
- swap函数：用于交换字符数组中的两个字符。
通过这些辅助函数，我们只需 3 步完成了字符串的左旋转操作。
复杂度分析
- 时间复杂度：三次翻转，每次 O(n)O(n)O(n)，因此总时间复杂度为 O(n)O(n)O(n)。
- 空间复杂度：操作在原字符串的字符数组上进行，因此空间复杂度为 O(1)O(1)O(1)。
😄总结
在这道题目中，使用三步翻转法避免了直接拼接带来的额外开销，使得操作更加高效简洁。无论是面试还是实际开发中，这种方法都非常实用。
这个题目很好地锻炼了对字符串操作和数组翻转的理解，三步翻转法的思路在其他字符串旋转、数组循环移位等问题中也能得到广泛应用。希望这篇文章能帮助大家掌握并熟练应用这种方法。
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞
