LeetCode541. Reverse String II

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:

1
2
Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

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

双指针

未命名1

my code in cpp

1
2
3
4
5
6
7
8
9
10
11
12
string reverseStr(string s, int k) {
if (s.empty()) return "";
for (int i = 0; i < s.size(); i += 2*k)//i +=2*k
{
int f = i,l = i + k - 1;
while (l >= s.size())
l--;
while (f < l)
swap(s[f++], s[l--]);
}
return s;
}

STL:reverse

LC in cpp

1
2
3
4
5
6
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += 2 * k) {
reverse(s.begin() + i, min(s.begin() + i + k, s.end()));
}
return s;
}

总结

  1. 双指针题,和LeetCode344. Reverse String一样,套路不变,细节不同。
  2. index按2*k递增。
  3. 每2k组中的l指针跟s.size()有关,一直到s的尾部,所以多了个while(…) l–。
  4. 用stl作弊的方法就不多说啦~
Thanks for Support.