模拟-反转字符串2

Problem: 541. 反转字符串 II

思路

模拟,以每2k个字符作为一段,反转其中前k个字符, 正好python列表若索引超出最长,则一直取到最长,进行前k个字符选择时可通过这个trick,保证小于k长度的最后一段被全部反转

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

Python 3版本代码

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        def swapk(res):
            n = len(res)
            for j in range(n//2):
                res[j], res[n-j-1] = res[n-j-1], res[j]
            return res
        n = len(s)
        res = list(s)

        for i in range(0, n, 2*k):
            res[i: i + k] = swapk(res[i: i + k])
        return ''.join(res)

C++ 版本代码

class Solution {
public:
    string reverseStr(string s, int k) {
        int len = s.size();
        for (int i=0; i<len; i += 2*k  ){
            if(i +k <s.size()){
                reverse(s.begin() + i, s.begin() + i + k);
            }
            else{
                reverse(s.begin()+i, s.begin()+s.size());
            }
            
        }
        return s;
    }
};