186. Reverse Words in a String II 🔒

DifficultyMedium

Description

Given a character array s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by a single space.

Your code must solve the problem in-place, i.e. without allocating extra space.

Example 1:

Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Example 2:

Input: s = ["a"]
Output: ["a"]

Constraints:

1 <= s.length <= 10⁵
s[i] is an English letter (uppercase or lowercase), digit, or space ' '.
There is at least one word in s.
s does not contain leading or trailing spaces.
All the words in s are guaranteed to be separated by a single space.

Solutions

Solution 1: Two Pointers

Thinking

Reverse the word order in a character array in place; words are separated by a single space. \(n\le 10^5\), \(O(1)\) extra space. Reverse each word, then reverse the whole array: word order flips and letters inside a word return to normal. Two pointers mark each word.

We can iterate through the character array \(s\), using two pointers \(i\) and \(j\) to find the start and end positions of each word, then reverse each word, and finally reverse the entire character array.

The time complexity is \(O(n)\), where \(n\) is the length of the character array \(s\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

class Solution:
    def reverseWords(self, s: List[str]) -> None:
        def reverse(i: int, j: int):
            while i < j:
                s[i], s[j] = s[j], s[i]
                i, j = i + 1, j - 1

        i, n = 0, len(s)
        for j, c in enumerate(s):
            if c == " ":
                reverse(i, j - 1)
                i = j + 1
            elif j == n - 1:
                reverse(i, j)
        reverse(0, n - 1)

class Solution {
    public void reverseWords(char[] s) {
        int n = s.length;
        for (int i = 0, j = 0; j < n; ++j) {
            if (s[j] == ' ') {
                reverse(s, i, j - 1);
                i = j + 1;
            } else if (j == n - 1) {
                reverse(s, i, j);
            }
        }
        reverse(s, 0, n - 1);
    }

    private void reverse(char[] s, int i, int j) {
        for (; i < j; ++i, --j) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
        }
    }
}

class Solution {
public:
    void reverseWords(vector<char>& s) {
        auto reverse = [&](int i, int j) {
            for (; i < j; ++i, --j) {
                swap(s[i], s[j]);
            }
        };
        int n = s.size();
        for (int i = 0, j = 0; j < n; ++j) {
            if (s[j] == ' ') {
                reverse(i, j - 1);
                i = j + 1;
            } else if (j == n - 1) {
                reverse(i, j);
            }
        }
        reverse(0, n - 1);
    }
};

func reverseWords(s []byte) {
    reverse := func(i, j int) {
        for ; i < j; i, j = i+1, j-1 {
            s[i], s[j] = s[j], s[i]
        }
    }
    i, n := 0, len(s)
    for j, c := range s {
        if c == ' ' {
            reverse(i, j-1)
            i = j + 1
        } else if j == n-1 {
            reverse(i, j)
        }
    }
    reverse(0, n-1)
}

/**
 Do not return anything, modify s in-place instead.
 */
function reverseWords(s: string[]): void {
    const n = s.length;
    const reverse = (i: number, j: number): void => {
        for (; i < j; ++i, --j) {
            [s[i], s[j]] = [s[j], s[i]];
        }
    };
    for (let i = 0, j = 0; j <= n; ++j) {
        if (s[j] === ' ') {
            reverse(i, j - 1);
            i = j + 1;
        } else if (j === n - 1) {
            reverse(i, j);
        }
    }
    reverse(0, n - 1);
}

186. Reverse Words in a String II 🔒

Description

Solutions

Solution 1: Two Pointers

Comments