字符串的左旋转和右旋转

在本文中，我们将探讨如何在 Python 中实现字符串的左旋和右旋。分步算法和代码示例将演示左右旋转字符串的机制。我们还将讨论字符串旋转有用的用例和应用。线性时间复杂度确保即使是大型字符串也能快速旋转。到最后，您应该对这项基本字符串操作有很好的掌握。

字符串是许多计算机科学和编程领域中使用的一种基本数据结构。通常，我们需要通过重新排列字符顺序来操作字符串。其中一项操作是字符串旋转，其中字符串中的字符会向左或向右旋转若干个位置。在左旋中，字符向左移动，而在右旋中，字符向右移动。

字符串旋转在密码学、递归编程练习和序列重排等多个领域都有应用。ROT13 和 Caesar 密码等加密算法使用旋转来加密和解密文本。在编码面试和在线练习中，字符串旋转通常会成为测试程序员技能的算法问题。

字符串的左旋

左旋是一种操作，其中字符串中的每个字符都向左移动指定的位置数。例如，如果我们将字符串“Hello”左旋 2 个位置，它会变成“love”。

左旋字符串的机制如下：

1. 首先，我们必须确定 n - 要旋转字符串的位置数。在我们的示例中，n 是 2。
2. 接下来，我们将原始字符串的前 n 个字符取出，并将其追加到字符串的末尾。对于“Hello”，前 2 个字符是“He”。
3. 现在我们将“He”追加到字符串的末尾，使其变成“love”。前 n 个字符现已旋转到末尾。
4. 最后，我们从原始字符串中删除前 n 个字符“He”。这会留下最终左旋的字符串“lloHe”。

总而言之，对于长度为 L 的字符串：

• 取前 n 个字符并将其追加到末尾
• 删除前 n 个字符

这会将字符串中的每个字符向左移动 n 个位置。

时间复杂度为 O(L)，因为字符串中的每个字符都被移动了一次。空间复杂度也为 O(L)，因为我们最多会创建一个长度为 L 的字符串副本。

左旋字符串在密码学中有应用。例如，ROT13 密码将每个字母旋转 13 个位置。这个简单的密码被用来保护通信。

因此，本质上，左旋是通过循环将字符向左移位来重新排列字符串。线性的时间和空间复杂度使其即使在处理大型输入时也很快。

Python 实现：简单方法

说明

• 定义一个名为 left_rotate 的函数，它接受字符串和要旋转的位置数 (n) 作为参数。
• 使用 len() 计算字符串的长度。这将在以后处理边缘情况时用到。
• 将 n 与长度 L 取模，将 n 限制在 0 到 L-1 之间。这可以防止边缘情况错误。
• 将字符串切片成两部分 - left_part 从 0 到 n，right_part 从 n 到末尾。
• 将 right_part 和 left_part 连接起来以获得旋转后的字符串。
• 返回旋转后的字符串。
• 通过传递字符串和 n 来调用 left_rotate。打印原始字符串和旋转后的字符串。

时间复杂度为 O(L)，用于切片字符串。空间复杂度为 O(L)，用于存储切片后的字符串。这可以在线性时间内处理任何字符串的旋转。

使用递归

说明

• 基本情况是当 n 达到 0 时；我们只需返回字符串。
• 计算字符串的长度 L 以处理边缘情况。
• 将 n 与 L 取模，将 n 限制在 0 到 L-1 之间。
• 通过切掉第一个字符并将其追加到末尾来递归调用 left rotate。
• 每次调用时将 n 减 1，直到达到基本情况。
• 返回旋转后的字符串。

在每次调用时，一个字符从开头移动到末尾。经过 n 次调用后，字符串就左旋了 n 个位置。

时间复杂度为 O(n)，因为我们递归了 n 次。空间复杂度为 O(n)，用于递归堆栈。

这演示了如何使用字符串切片递归地旋转字符串。线性的时间和空间复杂度使其高效。

右旋

右旋与左旋类似，只是字符向右移动而不是向左移动。

对于字符串“Hello”，将其右旋 2 个位置将得到“local”。最后 2 个字符“Lo”被移到开头，并且从末尾删除了“Lo”。

右旋字符串的步骤如下：

1. 确定 n - 要旋转的位置数。
2. 取出最后 n 个字符并将其添加到字符串的开头。
3. 从原始字符串中删除最后 n 个字符。

这会将字符串中的所有字符向右移动 n 个位置。

时间复杂度和空间复杂度为 O(L)，其中 L 是字符串的长度。

实施

有两种方法可以实现右旋：

迭代

1. 找到字符串的长度 L
2. 将 n 与 L 取模，将 n 限制在 0 到 L-1 之间
3. 切片最后 n 个字符并将其添加到开头
4. 从原始字符串中删除最后 n 个字符
5. 返回旋转后的字符串

迭代方法以 O(L) 的时间和空间复杂度旋转字符串。

递归

1. 基本情况：如果 n 为 0，则返回字符串。
2. 取最后一个字符，并将其添加到递归调用的字符串（不包括最后一个字符）之前。
3. 每次递归调用时将 n 减 1，直到 n 为 0。
4. 返回旋转后的字符串

递归方法也以 O(L) 的时间和空间复杂度通过递归地将最后一个字符添加到开头来旋转。

因此，总而言之，右旋将字符向右移动而不是向左移动。迭代和递归实现都具有线性的时间和空间复杂度。

Python 实现：迭代方法

说明

1. 定义 right_rotate 函数，它将字符串和旋转次数 n 作为参数。
2. 使用 len() 计算字符串的长度 L。稍后将使用此长度。
3. 使用 n = n % L 对 L 取模。这确保 n 限制在 0 到 L-1 之间，防止出现索引越界错误。
4. 将字符串的最后 n 个字符切片到一个名为 right 的子字符串中，使用 str[-n:]。
5. 将剩余的左侧字符切片到一个名为 left 的子字符串中，使用 str[:-n]。
6. 连接 right 和 left 子字符串以获得旋转后的字符串。
7. 返回旋转后的字符串。
8. 初始化示例字符串“Hello”和 n = 2。
9. 打印原始字符串。
10. 调用 right_rotate()，传递字符串和 n。打印返回的旋转后的字符串。

这会遍历字符串一次，因此时间复杂度和空间复杂度都是 O(L)。模运算处理了较大的 n 值时的错误。总而言之，它提供了一种简洁的右旋字符串迭代实现。

递归方法

说明

1. 定义 right_rotate 函数，它接受字符串和 n 作为参数。
2. 基本情况 - 如果 n 变为 0，则直接返回字符串。
3. 计算字符串的长度 L 以处理边缘情况。
4. 将 n 与 L 取模，将 n 限制在 0 到 L-1 之间。
5. 使用 str[-1] 递归调用 right_rotate，并将最后一个字符添加到开头。
6. 在递归之前使用 str[:-1] 切片字符串以排除最后一个字符。
7. 在每次递归调用时将 n 减 1，以趋向于基本情况。
8. 当达到基本情况 n == 0 时，展开并返回旋转后的字符串。
9. 初始化字符串“Hello”和 n = 2。
10. 打印原始字符串。
11. 调用 right_rotate()，传递字符串和 n。打印返回的字符串。

这会递归地将每个字符向右移动，直到 n 变为 0。在最坏的情况下，我们递归 n 次，因此时间复杂度和空间复杂度都是 O(n)。