Skip to content

Instantly share code, notes, and snippets.

@wayetan
Created March 9, 2014 20:39
Show Gist options
  • Save wayetan/9454206 to your computer and use it in GitHub Desktop.
Save wayetan/9454206 to your computer and use it in GitHub Desktop.
Reverse Words in a String
/**
* Given an input string, reverse the string word by word.
* For example,
* Given s = "the sky is blue",
* return "blue is sky the".
* Clarification:
* What constitutes a word?
***A sequence of non-space characters constitutes a word.
* Could the input string contain leading or trailing spaces?
***Yes. However, your reversed string should not contain leading or trailing spaces.
* How about multiple spaces between two words?
***Reduce them to a single space in the reversed string.
*/
public class Solution {
public String reverseWords(String s) {
if (s == null || s.length() == 0)
return "";
int curr = 0, start = 0;
s = reverse(s);
StringBuilder sb = new StringBuilder();
while (curr < s.length()) {
// start = curr;
if (s.charAt(curr) != ' ') {
// word
curr++;
} else {
if (start != curr) {
sb.append(reverse(s.substring(start, curr)) + " ");
start = curr;
} else {
// space;
curr++;
start++;
}
}
}
if (start != curr) {
sb.append(reverse(s.substring(start, curr)) + " ");
}
return sb.length() != 0 ? sb.toString().substring(0, sb.length() - 1) : "";
}
public String reverse(String s) {
if (s == null || s.length() == 0)
return "";
int length = s.length(), last = length - 1;
char[] chars = s.toCharArray();
for (int i = 0; i < length / 2; i++) {
char c = chars[i];
chars[i] = chars[last - i];
chars[last - i] = c;
}
return new String(chars);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment