557. Reverse Words in a String III【easy】

557. Reverse Words in a String III【easy】

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

解法一：

 1 class Solution {
 2 public:
 3     void reverseSelf(string & s, int start, int end)
 4     {
 5         while (start <= end) {
 6             char c = s[start];
 7             s[start] = s[end];
 8             s[end] = c;
 9             ++start;
10             --end;
11         }
12     }
13     
14     string reverseWords(string s) {
15         int i = 0;
16         
17         while (i < s.length()) {
18             int j = i;
19             while (j < s.length() && s[j] != ' ') {
20                 ++j;
21             }
22             
23             reverseSelf(s, i, j - 1);
24             
25             i = j + 1;
26         }
27         
28         return s;
29     }
30 };

无他，注意下标边界尔。

解法二：

 1 public String reverseWords(String s) 
 2 {
 3     char[] s1 = s.toCharArray();
 4     int i = 0;
 5     for(int j = 0; j < s1.length; j++)
 6     {
 7         if(s1[j] == ' ')
 8         {
 9             reverse(s1, i, j - 1);
10             i = j + 1;
11         }
12     }
13     reverse(s1, i, s1.length - 1);
14     return new String(s1);
15 }
16 
17 public void reverse(char[] s, int l, int r)
18 {
19     while(l < r)
20     {
21         char temp = s[l];
22         s[l] = s[r];
23         s[r] = temp;
24         l++; r--;
25     }
26 }

参考@sooryaprasanna 的代码

Step 1. Convert the string to char[] array
Step 2. Whenever I encounter a space ' ' , I call the reverse function ( just to keep the code clean )
Step 3. Repeat till the end!

解法三：

 1 class Solution {
 2 public:
 3     string reverseWords(string s) {
 4         for (int i = 0; i < s.length(); i++) {
 5             if (s[i] != ' ') {   // when i is a non-space
 6                 int j = i;
 7                 for (; j < s.length() && s[j] != ' '; j++) { } // move j to the next space
 8                 reverse(s.begin() + i, s.begin() + j);
 9                 i = j - 1;
10             }
11         }
12         
13         return s;
14     }
15 };

参考@alexander 的代码。

补充一下reverse函数：

reverse函数可以反转一个容器中的内容，包含在<algorithm>库中。

1、函数原型

reverse函数等同于下面的代码：

1 template <class BidirectionalIterator> void reverse (BidirectionalIterator first, BidirectionalIterator last)
2 {
3      while ((first!=last)&&(first!=--last))
4      {
5           std::iter_swap (first,last);
6           ++first;
7      }
8 }

reverse函数使用iter_swap来交换两个元素。

2、参数：first、last

first和last是双向迭代器类型，reverse函数反转的范围是[first,last)，所以包括first指向的元素，不包括last指向的元素。

3、返回值

reverse函数没有返回值。

参考自：http://blog.csdn.net/u012877472/article/details/49557077