This is the 20th day of my participation in the August More Text Challenge

Leetcode -541- Reverse string II

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

Given a string s and an integer k, invert the first K characters for 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 1:

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

Example 2:

Input: s = "abcd", k = 2Copy the code

Tip:

• 1 <= s.length <= 104
• S consists of lowercase English only
• 1 <= k <= 104

Related Topics

• Double pointer
• string
• 👍 👎 0 157

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Dual Pointers

• The fast or slow pointer moves
• Reverse characters

char[] chars;

public String reverseStr(String s, int k) {
    int n = s.length();
    chars = s.toCharArray();
    StringBuilder res = new StringBuilder();
    if (k >= n) {
        for (int i = n - 1; i >= 0; i--) {
            res.append(chars[i]);
        }
        return res.toString();
    }
    int l = 0;

    while (l + 2 * k < n) {
        res.append(reverse(s, l, l + 2 * k));
        l += 2 * k;
    }
    if (l + k < n) {
        for (int i = l + k - 1; i >= l; i--) {
            res.append(chars[i]);
        }
        l = l + k;
        for (inti = l; i < n; i++) { res.append(chars[i]); }}else {
        for (int i = n - 1; i >= l; i--) { res.append(chars[i]); }}return res.toString();
}

public String reverse(String s, int l, int r) {
    StringBuilder sb = new StringBuilder();
    for (int i = l + (r - l) / 2 - 1; i >= l; i--) {
        sb.append(chars[i]);
    }
    for (int i = l + (r - l) / 2; i < r; i++) {
        sb.append(chars[i]);
    }
    return sb.toString();
}
Copy the code

• Time complexity O(n)
• Space complexity O(n)

Idea 2: double pointer optimization

• So there’s a lot of code there’s nothing particularly valuable about this, right

char[] chars;

public String reverseStr(String s, int k) {
    int n = s.length();
    chars = s.toCharArray();
    StringBuilder res = new StringBuilder();
    int l = 0, r = l + k;
    while (r < n) {
        res.append(reverse(s, l, r));
        res.append(s, r, Math.min(r + k, n));
        l += 2 * k;
        r = l + k;
    }
    if (l < n) {
        res.append(reverse(s, l, n));
    }

    return res.toString();
}

public String reverse(String s, int l, int r) {
    StringBuilder sb = new StringBuilder();
    for (int i = r - 1; i >= l; i--) {
        sb.append(chars[i]);
    }
    return sb.toString();
}
Copy the code

• Time complexity O(n)
• Space complexity O(n)