String Algorithm: Reverse the first k characters for every 2k ch

  • 时间:2020-09-23 15:11:59
  • 分类:网络文摘
  • 阅读:86 次

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

Example:
Input: s = “abcdefg”, k = 2
Output: “bacdfeg”

Restrictions:
The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

The problem statement is actually a bit hard to understand, but once you get it, this problem is easy to solve.

How to Reverse string in C++ using std::reverse for the first k characters?

The std::C++ has a handy reverse method that takes two iterators, and reverse it. Thus, we can iterate from the start, and increment the step of 2*k, compute the range, which is then passed to the reverse function to do the work.

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            reverse(begin(s) + a, begin(s) + b);
        }
        return s;
    }
};
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            reverse(begin(s) + a, begin(s) + b);
        }
        return s;
    }
};

You can also use a two pointer to swap until they meet in the middle.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            int left = a, right =  b - 1;
            while (left < right) {
                swap(s[left ++], s[right --]);
            }
        }
        return s;
    }
};
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            int left = a, right =  b - 1;
            while (left < right) {
                swap(s[left ++], s[right --]);
            }
        }
        return s;
    }
};

Other string reversing algorithms:

  • How to Reverse Words in a String in Place using C++ std::reverse?
  • How to Reverse Words in a String?
  • How to Reverse Only Letters in a String?
  • How to Reverse Vowels of a String in C/C++?
  • Reverse String in C/C++

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
The Concurrent Programming Language: Cind  How to Design a Design Bounded Blocking Queue in Python using Th  The Unique Permutations Algorithm with Duplicate Elements  Python Coding Reference: index() and find() for string (substrin  Walking Robot Simulation Algorithm with Obstacles Detection  The Selection Sorting Algorithm in VBScript  Find the Queens That Can Attack the King  4 Bloggers Who Were Killed Because Of Their Content  Top Mobile Technology Trends for Bloggers  The Vital Common Sense Marketing Strategy You May Have Forgotten 
评论列表
添加评论