Reverse Words in a String 反转单词顺序

时间:2021-10-05 13:53:33
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".

Update (2015-02-12): For C programmers: Try to solve it in-place in O(1) space

使用API 复杂度

时间 O(N) 空间 O(N)

思路

将单词根据空格split开来存入一个字符串数组,然后将该数组反转即可。

注意

先用trim()将前后无用的空格去掉

用正则表达式" +"来匹配一个或多个空格

代码
  1. public class Solution {
  2. public String reverseWords(String s) {
  3. String[] words = s.trim().split(" +");
  4. int len = words.length;
  5. StringBuilder result = new StringBuilder();
  6. for(int i = len -1; i>=0;i--){
  7. result.append(words[i]);
  8. if(i!=0) result.append(" ");
  9. }
  10. return result.toString();
  11. }
  12. }
复制代码
双指针交换法 复杂度

时间 O(N) 空间 O(N) 如果输入时char数组则是O(1)

思路

先将字符串转换成char的数组,然后将整个数组反转。然后我们再对每一个单词单独的反转一次,方法是用两个指针记录当前单词的起始位置和终止位置,遇到空格就进入下一个单词。

代码
  1. public class Solution {
  2. public String reverseWords(String s) {
  3. s = s.trim();
  4. char[] str = s.toCharArray();
  5. // 先反转整个数组
  6. reverse(str, 0, str.length - 1);
  7. int start = 0, end = 0;
  8. for(int i = 0; i < s.length(); i++){
  9. if(str[i]!=' '){
  10. end++;
  11. } else {
  12. // 反转每个单词
  13. reverse(str, start, end - 1);
  14. end++;
  15. start = end;
  16. }
  17. }
  18. //反转最后一个单词,因为其后面没有空串
  19. reverse(str,start,str.length-1);


  20. return String.valueOf(str);
  21. }
  22. public void reverse(char[] str, int start, int end){
  23. while(start < end){
  24. char tmp = str[start];
  25. str[start] = str[end];
  26. str[end] = tmp;
  27. start++;
  28. end--;
  29. }
  30. }
  31. }
复制代码
Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example, Given s = "the sky is blue", return "blue is sky the". 
Could you do it in-place without allocating extra space?

双指针交换法 复杂度

时间 O(N) 空间 O(1)

思路

这题就是Java版的Inplace做法了,先反转整个数组,再对每个词反转。

代码
  1. public class Solution {
  2. public void reverseWords(char[] s) {
  3. reverse(s, 0, s.length - 1);
  4. int start = 0;
  5. for(int i = 0; i < s.length; i++){
  6. if(s[i] == ' '){
  7. reverse(s, start, i - 1);
  8. start = i + 1;
  9. }
  10. }
  11. reverse(s, start, s.length - 1);
  12. }
  13. public void reverse(char[] s, int start, int end){
  14. while(start < end){
  15. char tmp = s[start];
  16. s[start] = s[end];
  17. s[end] = tmp;
  18. start++;
  19. end--;
  20. }
  21. }
  22. }