Question

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 <= 104
• 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: Use Language Built-in Functions

We split the string into a list of strings by spaces, then reverse the list, and finally join the list into a string separated by spaces.

Time complexity $O(n)$, space complexity $O(n)$, where $n$ is the length of the string.

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);
  }
}

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 := strings.Split(s, " ")
  var ans []string
  for i := len(words) - 1; i >= 0; i-- {
    if words[i] != "" {
      ans = append(ans, words[i])
    }
  }
  return strings.Join(ans, " ")
}

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(" ")
  }
}

public class Solution {
  public string ReverseWords(string s) {
     return string.Join(" ", s.Trim().Split(" ").Where(word => !string.IsNullOrEmpty(word) && !string.IsNullOrEmpty(word.Trim())).Reverse());
  }
}

Solution 2: Two Pointers

We can use two pointers $i$ and $j$, each time we find a word, add it to the result list, then reverse the result list, and finally join the list into a string.

Time complexity $O(n)$, space complexity $O(n)$, where $n$ is the length of the string.

class Solution:
  def reverseWords(self, s: str) -> str:
    ans = []
    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
        ans.append(s[i:j])
        i = j
    return ' '.join(ans[::-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);
  }
}