541. Reverse string II

Given a string s and an integer k, you need to reverse the first k characters every 2k characters from the beginning of the string.

If there are less than k characters left, all the remaining characters are reversed. If the remaining characters are less than 2K but greater than or equal to K, the first K characters are reversed and the remaining characters are left as is.

Example: Input: s = "abcdefg", k = 2 Output: "bacdfeg"Copy the code

Tip:

  1. The string contains only lowercase English letters.
  2. The given string length and k are in the range [1, 10000].

Method 1: double pointer method

Algorithm idea:

  • Every 2k is a group, the first K elements are reversed, the last k elements remain unchanged;
  • The subscript of the first k elements is :(I, I +k-1), which needs to determine whether the range of the array is exceeded.
  • After the current inversion I = I + 2k, the next group of inversion;

Reference Code 1:

class Solution { public String reverseStr(String s, int k) { char[] chars = s.toCharArray(); int n = chars.length; For (int I = 0; i < n; i += 2 * k) { int left = i; Int right = I + k - 1 < n? i + k - 1 : n -1; While (left < right) {char temp = chars[left]; chars[left++] = chars[right]; chars[right--] = temp; } } return String.valueOf(chars); }}Copy the code

Complexity analysis:

  • Time complexity: O(n)O(n)O(n). Where N is the magnitude of s. We create an auxiliary array that flips half the characters of s.
  • Space complexity: O(1)O(1)O(1).

Method 2: The built-in reverse method

Reference Code 2:

class Solution { public String reverseStr(String s, int k) { int start = 0, end = s.length() - 1; StringBuilder sb = new StringBuilder(); While (start <= end) {// Number of remaining characters int size = end-start + 1; if (size < k) { sb.append(new StringBuilder(s.substring(start)).reverse()); } else {sb.appEnd (new StringBuilder(s.subString (start, start + k)).reverse()); Sb.append (new StringBuilder(s.substring(start + k, start+ math. min(size, 2 * k)))); } start += 2 * k; } return sb.toString(); }}Copy the code

Some pictures from the network, copyright to the original author, delete.Copy the code