[344. Reverse string]

“This is the 10th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Topic describes

Write a function that reverses the input string. The input string is given as a character array s.

Instead of allocating extra space to another array, you must modify the input array in place, using O(1) extra space to solve the problem.

The sample

Example 1:

Input: s = "h", "e", "l", "l", "o"] output: [" o ", "l", "l", "e", "h"]Copy the code

Example 2:

Input: s = "H", "a", "n", "n", "a", "H"] output: [" H ", "a", "n", "n", "a", "H"]Copy the code

Tip:

• 1 <= s.length <= 105
• s[i]Are allASCIIPrintable characters in a code table

Train of thought

This problem is actually the implementation of the library function reserve, you can call it directly to complete the problem, but lose the meaning of the brush problem. Today to introduce a kind of algorithm idea: double pointer. In general, it is mainly used for linear data structures, such as groups of numbers, strings, linked lists, etc. Today’s problem is the easiest problem on strings. It also helps us to analyze the double pointer problem. So today we’re going to start by looking at strings. For today’s problem, it’s easy to think of using a double-pointer method, where you define two Pointers (or index subscripts), one to the front of the string and one to the back of the string, and move both Pointers to the middle and swap elements. , time complexity is O(n)O(n)O(n). In addition to flip a class of problems can also use the stack to achieve, but not as good as the double pointer method.

Code implementation

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i=0,j=s.size(a)- 1; i<s.size(a) /2; i++,j--){// I before the string, j after the string
            swap(s[i],s[j]);                 // Swap the contents of the pointer}}};Copy the code

In general, at the code level, a double pointer must define two Pointers that move through a loop, and under certain conditions, such as meeting, reaching the end, and so on, will satisfy our expectations. And you can see that in fact, double Pointers are two for loops in one for loop without moving towards the middle. It’s just that it’s not obvious, and we’ll do more problems in the future.

conclusion

The above content uses the algorithm idea of double pointer to realize the library function Reserve, and briefly introduces the double pointer.