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.
Example 4:
Input: s = " Bob Loves Alice " Output: "Alice Loves Bob"
Example 5:
Input: s = "Alice does not even like bob" Output: "bob like even not does Alice"
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?
Solution: Stack
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: string reverseWords(string s) { stringstream ss(s); stack<string> st; string w; while (ss >> w) st.push(w); string ans; while (!st.empty()) { ans += st.top(); st.pop(); if (!st.empty()) ans += ' '; } return ans; } }; |
Solution: In-Place
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: string reverseWords(string& s) { reverse(begin(s), end(s)); int l = 0; for (int i = 0, j = 0; i < s.length(); ++i) { if (s[i] == ' ') continue; if (l) ++l; j = i; while (j < s.length() && s[j] != ' ') ++j; reverse(begin(s) + l, begin(s) + j); l += (j - i); i = j; } s.resize(l); return s; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment