Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

Given a string S, return the “reversed” string, where non-alphabetic characters are left in place and all letter positions are reversed.

The sample

Input: "ab-cd" Output: "DC-BA"Copy the code
Input: "A-bC-def-ghij" Output: "J-iH-gFE-dcba"Copy the code
Input: "Test1ng - when = code - Q!" Output: "Qedo1ct - eeLg = ntse - T!"Copy the code

prompt

  1. S.length <= 100
  2. 33 <= S[i].ASCIIcode <= 122 
  3. SContains no\ or "

Their thinking

Double pointer

To flip a string, leave the characters in place except for the letters. So instead of swapping the first and last elements, we have to add an extra layer of judgment, skip the non-letter parts, and swap.

  1. Convert strings into byte arrays for easy element swapping;
  2. defineleft, rightTwo Pointers;
  3. Check whether it is a letter or not.Character.isLetter(char c)).
class Solution {
    public String reverseOnlyLetters(String s) {
        // Convert to an array
        char[] sChar = s.toCharArray();
        // Define a pointer
        int left = 0, right = sChar.length - 1;
        // go through the number group
        while(left < right){
            // Skip the non-letter parts on the left
            while(left < right && ! Character.isLetter(sChar[left])){ ++left; }// Skip the non-letter parts on the right
            while(left < right && ! Character.isLetter(sChar[right])){ --right; }// Swap elements
            char c = sChar[left];
            sChar[left++] = sChar[right];
            sChar[right--] = c;
        }
        // Reconvert the byte array into a string and return it
        return newString(sChar); }}Copy the code

Complexity analysis

  • Time complexity: O(N)O(N)O(N)
  • Space complexity: O(N)O(N)O(N)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/re…