In this guide, you will get 151. Reverse Words in a String LeetCode Solution with the best time and space complexity. The solution to Reverse Words in a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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?
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
151. Reverse Words in a String LeetCode Solution in C++
class Solution {
public:
string reverseWords(string s) {
ranges::reverse(s); // Reverse the whole string.
reverseWords(s, s.length()); // Reverse each word.
return cleanSpaces(s, s.length()); // Clean up the spaces.
}
private:
void reverseWords(string& s, int n) {
int i = 0;
int j = 0;
while (i < n) {
while (i < j || i < n && s[i] == ' ') // Skip the spaces.
++i;
while (j < i || j < n && s[j] != ' ') // Skip the spaces.
++j;
reverse(s.begin() + i, s.begin() + j); // Reverse the word.
}
}
// Trim leading, trailing, and middle spaces
string cleanSpaces(string& s, int n) {
int i = 0;
int j = 0;
while (j < n) {
while (j < n && s[j] == ' ') // Skip the spaces.
++j;
while (j < n && s[j] != ' ') // Keep non spaces
s[i++] = s[j++];
while (j < n && s[j] == ' ') // Skip the spaces.
++j;
if (j < n) // Keep only one space.
s[i++] = ' ';
}
return s.substr(0, i);
}
};
/* code provided by PROGIEZ */
151. Reverse Words in a String LeetCode Solution in Java
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder(s).reverse(); // Reverse the whole string.
reverseWords(sb, sb.length()); // Reverse each word.
return cleanSpaces(sb, sb.length()); // Clean up the spaces.
}
private void reverseWords(StringBuilder sb, int n) {
int i = 0;
int j = 0;
while (i < n) {
while (i < j || i < n && sb.charAt(i) == ' ') // Skip the spaces.
++i;
while (j < i || j < n && sb.charAt(j) != ' ') // Skip the spaces.
++j;
reverse(sb, i, j - 1); // Reverse the word.
}
}
// Trim leading, trailing, and middle spaces
private String cleanSpaces(StringBuilder sb, int n) {
int i = 0;
int j = 0;
while (j < n) {
while (j < n && sb.charAt(j) == ' ') // Skip the spaces.
++j;
while (j < n && sb.charAt(j) != ' ') // Keep non spaces
sb.setCharAt(i++, sb.charAt(j++));
while (j < n && sb.charAt(j) == ' ') // Skip the spaces.
++j;
if (j < n) // Keep only one space.
sb.setCharAt(i++, ' ');
}
return sb.substring(0, i).toString();
}
private void reverse(StringBuilder sb, int l, int r) {
while (l < r) {
final char temp = sb.charAt(l);
sb.setCharAt(l++, sb.charAt(r));
sb.setCharAt(r--, temp);
}
}
}
// code provided by PROGIEZ
151. Reverse Words in a String LeetCode Solution in Python
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(reversed(s.split()))
# code by PROGIEZ
