Welcome to Subscribe On Youtube

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.

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.

• Java
• C++
• Python
• Go
• TypeScript
• C#
• RenderScript

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

• class Solution:
      def reverseWords(self, s: str) -> str:
          words = s.strip().split()
          return ' '.join(words[::-1])
  
  ############
  
  
  class Solution: # O(1) space complexity
      def reverseWords(self, s: str) -> str:
          # Remove leading and trailing spaces
          s = s.strip()
  
          # Reverse the entire string
          s = self.reverseString(s, 0, len(s) - 1)
  
          # Reverse each word in the string
          start = 0
          end = 0
          while end < len(s):
              if s[end] == ' ':
                  s = self.reverseString(s, start, end - 1)
                  start = end + 1
              end += 1
  
          # Reverse the last word
          s = self.reverseString(s, start, end - 1)
  
          return s
  
      def reverseString(self, s: str, start: int, end: int) -> str:
          # Convert the string to a list of characters
          chars = list(s)
  
          # Reverse the substring
          while start < end:
              chars[start], chars[end] = chars[end], chars[start]
              start += 1
              end -= 1
  
          # Convert the list of characters back to a string
          return ''.join(chars)
  
  ############
  
  class Solution(object):
    def reverseWords(self, s):
      """
      :type s: str
      :rtype: str
      """
      return " ".join(s.split()[::-1])
  
  

• 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(' ');
  }
  
  

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

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

All Problems

All Solutions