Two ways to invert the character order of words in a string

Problem description

When dealing with string-related problems, inverting the character order of each word in a string is a common task, and it is necessary to ensure that the initial order of spaces and words remains unchanged.

Given a strings, you need to reverse the character order of each word in the string while still retaining the spaces and the initial order of the words.

• sContains printableASCIICharacters.
• sNo beginning or ending spaces are included.
• sinsideAt leastThere is a word.
• sAll words in it are separated by a space.

Below we will introduce two methods to solve this problem in detail, including its problem-solving ideas and specific implementation details.

Solution based on fast and slow pointer

1. Problem-solving ideas

Fast and slow pointers are a common technique. In this question, fast pointers are used to traverse strings, and slow pointers are used to mark the starting position of each word.

When a fast pointer encounters a space, it means that a word has been traversed. At this time, the characters between the slow pointer and the fast pointer can be reversed.

After traversing the complete string, you also need to invert the last word because there are no spaces after the last word to trigger the inversion operation. At the same time, this also deals with the situation of only one word

2. Code implementation

class Solution {
public:
    string reverseWords(string s) //Fast and Slow Pointer Solution    {
        string::iterator fast = ();
        string::iterator slow = ();
 
        while( fast != () )//The pointer is over and ends        {
            if(*fast==' ') //The fast pointer goes to the space position and stops, reverses the letters of this part.            {
                reverse(slow,fast);
                slow = fast+1;
            }
            ++fast;
        }
        reverse(slow,fast);// When the loop is out, the slow pointer remains in the first letter of the last word                           //The fast pointer is in the \0 position and needs to be reversed once more        // At the same time, it can be processed with strings of only one word        return s;
 
    }
};

3. Code details analysis

• Pointer initialization: First, the fast pointer fast and slow pointer slow are defined, and they are both initialized as the starting position of the string s ().
• Traversing the string:By looping through while, the loop continues as long as the fast pointer fast does not reach the end of the string ().
• Word reversal: When the character pointed to by fast pointer fast is a space, it means that a word has been traversed. At this time, call the reverse function to invert the characters between slow pointer slow to fast pointer fast. Then move the slow pointer slow to the starting position of the next word, i.e. fast + 1.
• The last word processing:After the loop is over, the slow pointer slow stays at the start position of the last word, and the fast pointer fast points to the next position at the end of the string (i.e. the position of \0). At this time, the reverse function is called again to invert the last word.
• Return result: Finally, return the inverted string s.

Index-based solution

1. Problem-solving ideas

This method uses an index to traverse the string, record the starting position of each word through a variable, and inverts the current word when encountering a space or ending a string.

2. Code implementation

#include <iostream>
#include <string>
#include <algorithm>
 
class Solution {
public:
    string reverseWords(string s) {
        int start = 0; // Slow pointer, marking the starting position of each word        for (int end = 0; end <= (); ++end) {
            // When a space or string is encountered, reverse the current word            if (end == () || s[end] == ' ') {
                // Invert the character from start to end - 1                std::reverse(() + start, () + end);
                // Update slow pointer to the starting position of the next word                start = end + 1;
            }
        }
        return s;
    }
};

3. Code details analysis

• Start position initialization:Define the variable start to record the starting position of each word, initialized to 0.
• Traversing the string:Through a for loop, use the variable end to traverse the string s, with the loop condition end <= (), which ensures that the last word can be processed at the end of the string.
• Word reversal:When end is equal to the length of the string () or s[end] is a space, it means that a word has been traversed. At this time, calling the std::reverse function will invert the characters from () + start to () + end.
• Update start location:After reversing the current word, update start to end + 1, which is the starting position of the next word.
• Return result:After the loop is finished, the inverted string s is returned.

Comparison of the two methods

• Time complexity:The time complexity of both methods is O(n), where n is the length of the string, because both need to traverse the string once and each character is inverted at most once.
• Space complexity:The spatial complexity of both methods is O(1), because only the additional space of constant orders is used.
• Code readability: Index-based method code is relatively concise, and using indexes to process strings is more intuitive, while fast and slow pointers-based methods require a good understanding of pointer operation.

Through the detailed introduction of the above two methods, we can choose appropriate methods based on specific needs and personal habits to solve the problem of inverting the order of word characters in strings.

This is the article about two methods of inverting the character order of words in C++ strings. For more related content on C++ inverting the character order of words, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!