151. Reverse Words in a String

Description

Given an input string 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 at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 10⁴
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Solutions

Solution 1: Two Pointers

Thinking

Reverse the word order and collapse extra spaces. \(n\le 10^4\). Two pointers skip spaces, cut out each word, then reverse the list and join. Leading, trailing, and repeated spaces disappear.

We can use two pointers \(i\) and \(j\) to find each word, add it to the result list, then reverse the result list, and finally concatenate it into a string.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the string.

Python3JavaC++GoTypeScriptRustC#

class Solution:
    def reverseWords(self, s: str) -> str:
        words = []
        i, n = 0, len(s)
        while i < n:
            while i < n and s[i] == " ":
                i += 1
            if i < n:
                j = i
                while j < n and s[j] != " ":
                    j += 1
                words.append(s[i:j])
                i = j
        return " ".join(words[::-1])

class Solution {
    public String reverseWords(String s) {
        List<String> words = new ArrayList<>();
        int n = s.length();
        for (int i = 0; i < n;) {
            while (i < n && s.charAt(i) == ' ') {
                ++i;
            }
            if (i < n) {
                StringBuilder t = new StringBuilder();
                int j = i;
                while (j < n && s.charAt(j) != ' ') {
                    t.append(s.charAt(j++));
                }
                words.add(t.toString());
                i = j;
            }
        }
        Collections.reverse(words);
        return String.join(" ", words);
    }
}

class Solution {
public:
    string reverseWords(string s) {
        int i = 0;
        int j = 0;
        int n = s.size();
        while (i < n) {
            while (i < n && s[i] == ' ') {
                ++i;
            }
            if (i < n) {
                if (j != 0) {
                    s[j++] = ' ';
                }
                int k = i;
                while (k < n && s[k] != ' ') {
                    s[j++] = s[k++];
                }
                reverse(s.begin() + j - (k - i), s.begin() + j);
                i = k;
            }
        }
        s.erase(s.begin() + j, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

func reverseWords(s string) string {
    words := []string{}
    i, n := 0, len(s)
    for i < n {
        for i < n && s[i] == ' ' {
            i++
        }
        if i < n {
            j := i
            t := []byte{}
            for j < n && s[j] != ' ' {
                t = append(t, s[j])
                j++
            }
            words = append(words, string(t))
            i = j
        }
    }
    for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
        words[i], words[j] = words[j], words[i]
    }
    return strings.Join(words, " ")
}

function reverseWords(s: string): string {
    const words: string[] = [];
    const n = s.length;
    let i = 0;
    while (i < n) {
        while (i < n && s[i] === ' ') {
            i++;
        }
        if (i < n) {
            let j = i;
            while (j < n && s[j] !== ' ') {
                j++;
            }
            words.push(s.slice(i, j));
            i = j;
        }
    }
    return words.reverse().join(' ');
}

impl Solution {
    pub fn reverse_words(s: String) -> String {
        let mut words = Vec::new();
        let s: Vec<char> = s.chars().collect();
        let mut i = 0;
        let n = s.len();

        while i < n {
            while i < n && s[i] == ' ' {
                i += 1;
            }
            if i < n {
                let mut j = i;
                while j < n && s[j] != ' ' {
                    j += 1;
                }
                words.push(s[i..j].iter().collect::<String>());
                i = j;
            }
        }

        words.reverse();
        words.join(" ")
    }
}

public class Solution {
    public string ReverseWords(string s) {
        List<string> words = new List<string>();
        int n = s.Length;
        for (int i = 0; i < n;) {
            while (i < n && s[i] == ' ') {
                ++i;
            }
            if (i < n) {
                System.Text.StringBuilder t = new System.Text.StringBuilder();
                int j = i;
                while (j < n && s[j] != ' ') {
                    t.Append(s[j++]);
                }
                words.Add(t.ToString());
                i = j;
            }
        }
        words.Reverse();
        return string.Join(" ", words);
    }
}

Solution 2: String Split

Thinking

Solution 1 splits words by hand. A built-in split on whitespace already drops extra spaces; reverse that list and join. Shorter code, same complexity.

We can use the built-in string split function to split the string into a list of words by spaces, then reverse the list, and finally concatenate it into a string.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the string.

Python3JavaGoTypeScriptRust

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.split()))

class Solution {
    public String reverseWords(String s) {
        List<String> words = Arrays.asList(s.trim().split("\\s+"));
        Collections.reverse(words);
        return String.join(" ", words);
    }
}

func reverseWords(s string) string {
    words := strings.Fields(s)
    for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
        words[i], words[j] = words[j], words[i]
    }
    return strings.Join(words, " ")
}

function reverseWords(s: string): string {
    return s.trim().split(/\s+/).reverse().join(' ');
}

impl Solution {
    pub fn reverse_words(s: String) -> String {
        s.split_whitespace().rev().collect::<Vec<&str>>().join(" ")
    }
}