0151. Reverse Words in a String
Medium | String + Stack | 8 ms (99.84%), 13.9 MB (43.36%)
Source: LeetCode - Reverse Words in a String GitHub: Solution / Performance
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.
Constraints:
1 <= s.length <= 10^4scontains English letters (upper-case and lower-case), digits, and spaces' '.There is at least one word in
s.
Input: s = "the sky is blue"
Output: "blue is sky the"
Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
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.
Input: s = " Bob Loves Alice "
Output: "Alice Loves Bob"
Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"class Solution:
def reverseWords(self, s: str) -> str:
# ==================================================
# String =
# ==================================================
# time : O(n), n is the length of s
# space : O(m), m is the number of words in s
l, r = 0, len(s) - 1
while s[l] == ' ': l += 1
while s[r] == ' ': r -= 1
words, word = [], ''
while l <= r:
if s[l] == ' ':
if word: words.append(word)
word = ''
l += 1
continue
word += s[l]
l += 1
if word: words.append(word)
ans = ''
for i in range(len(words)-1, -1, -1):
ans += words[i] + ' '
return ans[:-1]
'''
def reverseWords(self, s: str) -> str:
return ' '.join( reversed( s.split() ) )
'''class Solution {
/**
* @time : O(n), n is the length of input string
* @space : O(m), m is the number of words in the input string
*/
public String reverseWords(String s) {
int l = 0, r = s.length() - 1;
while(l <= r && s.charAt(l) == ' ') ++l;
while(l <= r && s.charAt(r) == ' ') --r;
Deque<String> d = new ArrayDeque();
StringBuilder word = new StringBuilder();
while(l <= r) {
char c = s.charAt(l);
if((word.length() != 0) && (c == ' ')) {
d.offerFirst(word.toString());
word.setLength(0);
} else if(c != ' ') {
word.append(c);
}
++l;
}
d.offerFirst(word.toString());
return String.join(" ", d);
}
}Last updated
Was this helpful?