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 ' '
.s
.
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1)
extra space?
This problem involves reversing the order of words in a given string. The key challenges are handling leading/trailing spaces and multiple spaces between words. The optimal solution should achieve this with linear time complexity O(n) and ideally, constant extra space O(1) if the language allows in-place modification. However, most solutions below achieve O(n) time and O(n) space.
This approach iterates through the string using two pointers:
i
): Skips leading spaces and finds the start of a word.j
): Finds the end of the current word by iterating until a space is encountered.i
and j
represents a word, which is added to a list (words
).words
list is reversed, and its elements are joined with single spaces to form the final reversed string.Time Complexity: O(n) - The string is traversed once in the outer loop, and the reverse operation takes O(m) where m is the number of words (m <= n). Therefore, the overall complexity remains linear.
Space Complexity: O(n) - In the worst case, the words
list could store all characters of the input string (if each character is a separate word).
This approach leverages built-in string functions:
s.split()
(or equivalent). The trim()
method is used to handle leading and trailing spaces, and a regular expression (\s+
) ensures that multiple spaces are treated as single delimiters.reversed()
(or equivalent).Time Complexity: O(n) - Splitting, reversing, and joining operations typically have linear time complexity. The efficiency depends on the underlying implementation of the string manipulation functions used.
Space Complexity: O(n) - Similar to Approach 1, the intermediate list of words could occupy linear space.
The previous response provided code examples in several languages implementing both approaches. The comments within those code snippets further explain the logic. Here's a summary of languages covered:
These examples demonstrate how both approaches can be implemented in various programming languages. The choice between the two approaches may depend on factors such as language features, readability preferences, and potential performance variations for very large inputs (though in most cases, the difference would be negligible). Approach 2 (string splitting) is often considered more concise and easier to read.