Question

Formatted question description: https://leetcode.ca/all/151.html

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?

Algorithm

First flip the entire string once, and then flip each word separately (or flip each word separately, and then flip the entire string once).

If we use Java’s String split function to do it, it is very simple, there are not so many moths, simple and clear.

we first call the original string to trim() to remove redundant spaces,
and then call split() to separate , The delimiter is set to "\\s+", this is actually a regular expression, \\s means space character, + means there can be one or more space characters,
then we can separate the words into one character in the string array, then we start from the end, take out the words one by one and add them to the result res, and add space characters between the words.
- Note that we leave the first word, and then add it when returning.

Code

public class Reverse_Words_in_a_String {

    public class Solution {
        public String reverseWords(String s) {

            if (s == null || s.length() == 0) {
                return s;
            }

            String res = "";
            String[] words = s.trim().split("\\s+");
            for (int i = words.length - 1; i > 0; --i) {
                res += words[i] + " ";
            }
            return res + words[0];
        }
    }

    public class Solution_sb {
        public String reverseWords(String s) {
            String res = "";
            String[] words = s.trim().split("\\s+");
            for (int i = words.length - 1; i > 0; --i) {
                res += words[i] + " ";
            }
            return res + words[0];
        }
    }

    // basically, 1st scan to reverse whole string including space,
    // 2nd scan to reverse each word when encountering a space
    public class Solution_2Scan {
        public String reverseWords(String s) {

            if (s == null || s.length() == 0) {
                return s;
            }

            int storeIndex = 0, n = s.length();
            StringBuilder sb = new StringBuilder(s).reverse();
            for (int i = 0; i < n; ++i) {
                if (sb.charAt(i) != ' ') {
                    if (storeIndex != 0) sb.setCharAt(storeIndex++, ' ');
                    int j = i;
                    while (j < n && sb.charAt(j) != ' ') sb.setCharAt(storeIndex++, sb.charAt(j++));
                    String t = new StringBuilder(sb.substring(storeIndex - (j - i), storeIndex)).reverse().toString();
                    sb.replace(storeIndex - (j - i), storeIndex, t);
                    i = j;
                }
                // else, skip space
            }
            sb.setLength(storeIndex);
            return sb.toString();

        }
    }
}

############

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

// OJ: https://leetcode.com/problems/reverse-words-in-a-string/
// Time: O(S)
// Space: O(1)
class Solution {
public:
    void reverseWords(string &s) {
        int i = 0, j = 0;
        while (j < s.size()) {
            while (j < s.size() && s[j] == ' ') ++j;
            if (i != 0 && j != s.size()) s[i++] = ' ';
            while (j < s.size() && s[j] != ' ') s[i++] = s[j++];
        }
        s.erase(i);
        i = j = 0;
        while (i < s.size()) {
            j = i;
            while (j < s.size() && s[j] != ' ') ++j;
            reverse(s.begin() + i, s.begin() + j);
            i = j + 1;
        }
        reverse(s.begin(), s.end());
    }
};

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])

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

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

151 - Reverse Words in a String

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions