Finger Offer 58-i. Flip word order

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

Enter a sentence in English and reverse the order of the words in the sentence, but not the order of the characters in the word. For simplicity, punctuation marks are treated like ordinary letters. For example, enter the string “I am a student. “, then print “student.

Example 1:

Input:"the sky is blue"Output:"blue is sky the"
Copy the code

Description:

Blank characters form a word.
An input string can contain extra Spaces before or after it, but not inverted characters.
If there is extra space between two words, reduce the space between the inverted words to only one.

Ideas:

Consider violence solving using native apis first. To remove excess whitespace before, after, and in between, use trim and replace methods, respectively. Replace replaces excess whitespace with a re.

It then splits into arrays, flips them, merges them into new strings and returns them.

Violence law

/ * * *@param {string} s
 * @return {string}* /
var reverseWords = function(s) {
    return s.trim().replace(/\x20+/g.' ').split(' ').reverse().join(' ');
};
Copy the code

Time complexity O(n).
Space complexity O(n).

Analysis:

Although the brute force method can be solved, it is not recommended to use this method in real interviews and can only be explained as an additional idea.

Double pointer

This problem can be solved by the method of double pointer.

/ * * *@param {string} s
 * @return {string}* /
var reverseWords = function(s) {
    s = s.trim(); // Remove the leading and trailing Spaces
    let i = s.length - 1; // Initializes the left edge of the word
    let j = i; // Initializes the right boundary of the word
    let result = []; // Initialize the result array
    while(i >= 0) { // The left margin of the word is less than 0 to terminate the loop
        while(i >= 0&& s[i] ! = =' ') i--; // Find the left edge of the word
        result.push(s.slice(i + 1, j + 1)); // Put the word in the result array
        while(i >= 0 && s[i] === ' ') i--; // Skip the gaps between words
        j = i; // Resets the right boundary of the word
    }
    return result.join(' '); // The result array is concatenated into a string
};
Copy the code

Time complexity O(n).
Space complexity O(n).

Analysis:

You first need to remove the leading and trailing whitespace of the string.

We then declare two Pointers to the left and right edges of the word.

It then loops through the string in reverse order. Start by holding the right edge still and look for the left edge of each word until you encounter a space. At this point, s.ice (I + 1, j + 1) is intercepted and placed in the result array. Then look for the right edge of the next word and reset the index of the right edge.

You can split the string by word and flip the word at the same time by adding the left and right word boundaries in reverse order. Finally concatenate the resulting array into a string and return it.

conclusion

Double Pointers are preferred for solving this problem. The extra note is the line where the string intercepts the word.

Since the slice method is closed and open, I — is executed when the left edge of the word is found, so the first argument needs to be I + 1; The right edge of the word is j, but it does not contain j, so the second argument needs j + 1.

In the implementation, it is reflected as follows: the I pointer moves continuously to the left, and when the left boundary of the word is found, the word is put into the result array; Resets the j pointer to the right boundary of the word when the right boundary of the next word is found. Enter the next loop and repeat the logic until I < 0.

Finger Offer 58-i. Flip word order