跳转至

剑指 Offer 58 - II. 左旋转字符串#

问题描述#

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

 

示例 1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

 

限制：

  • 1 <= k < s.length <= 10000

解题思路#

原地改变。

abcdefg --> cdefgab。

翻转: cdefg|ab --> ba|gfedc。

所以 ab|cdefg --> ba|gfedc --> cdefg|ab

可以看出，先分别翻转前后两部分，再整体翻转就可以得到结果。

Python 字符串是不可变类型，需要先转为列表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from typing import List


class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        def reverse(arr: List[str], l: int, r: int) -> None:
            while l < r:
                arr[l], arr[r] = arr[r], arr[l]
                l, r = l + 1, r - 1

        arr = list(s)
        reverse(arr, 0, n - 1)
        reverse(arr, n, len(s) - 1)
        reverse(arr, 0, len(s) - 1)
        return "".join(arr)
返回顶部

在手机上阅读