0151. Reverse Words in a String
https://leetcode.com/problems/reverse-words-in-a-string
Description
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?
ac
it's so stupid not being able to use trim(), split().
public class Solution {
public String reverseWords(String s) {
// edge case
if (s.length() == 0) return "";
char[] chars = s.toCharArray();
// clean space
int len = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == ' ' && (i == 0 || chars[i-1] == ' ')) continue;
chars[len] = chars[i];
len++;
}
if (len == 0) return ""; // all empty
if(chars[len-1] == ' ') len = len - 1;
// reverse whole string
reverse(chars, 0, len-1);
/// reverse each word
int k = 0, j = 0;
for (; k < len; k++) {
if (chars[k] != ' ') continue;
reverse(chars, j, k-1);
j = k+1;
}
if (k == len) reverse(chars, j, k-1);
// append to sb
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append(chars[i]);
}
return sb.toString();
}
private void reverse(char[] chars, int s, int e) {
while (s < e) {
char tmp = chars[s];
chars[s] = chars[e];
chars[e] = tmp;
s++;
e--;
}
}
}
Last updated
Was this helpful?