|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -/** |
4 | | - * 186. Reverse Words in a String II |
5 | | -
|
6 | | - Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. |
7 | | -
|
8 | | - The input string does not contain leading or trailing spaces and the words are always separated by a single space. |
9 | | -
|
10 | | - For example, |
11 | | - Given s = "the sky is blue", |
12 | | - return "blue is sky the". |
13 | | -
|
14 | | - Could you do it in-place without allocating extra space? |
15 | | - */ |
16 | 3 | publicclass_186 { |
17 | | -publicstaticclassSolution1 { |
18 | | -publicvoidreverseWords(char[]s) { |
19 | | -// Three steps to reverse |
20 | | -// 1, reverse the whole sentence |
21 | | -reverse(s,0,s.length -1); |
22 | | -// 2, reverse each word |
23 | | -intstart =0; |
24 | | -for (inti =0;i <s.length;i++) { |
25 | | -if (s[i] ==' ') { |
26 | | -reverse(s,start,i -1); |
27 | | -start =i +1; |
| 4 | +publicstaticclassSolution1 { |
| 5 | +publicvoidreverseWords(char[]s) { |
| 6 | +// Three steps to reverse |
| 7 | +// 1, reverse the whole sentence |
| 8 | +reverse(s,0,s.length -1); |
| 9 | +// 2, reverse each word |
| 10 | +intstart =0; |
| 11 | +for (inti =0;i <s.length;i++) { |
| 12 | +if (s[i] ==' ') { |
| 13 | +reverse(s,start,i -1); |
| 14 | +start =i +1; |
| 15 | + } |
| 16 | + } |
| 17 | +// 3, reverse the last word, if there is only one word this will solve the corner case |
| 18 | +reverse(s,start,s.length -1); |
| 19 | + } |
| 20 | + |
| 21 | +privatevoidreverse(char[]s,intstart,intend) { |
| 22 | +while (start <end) { |
| 23 | +chartemp =s[start]; |
| 24 | +s[start++] =s[end]; |
| 25 | +s[end--] =temp; |
| 26 | + } |
28 | 27 | } |
29 | | - } |
30 | | -// 3, reverse the last word, if there is only one word this will solve the corner case |
31 | | -reverse(s,start,s.length -1); |
32 | 28 | } |
33 | 29 |
|
34 | | -privatevoidreverse(char[]s,intstart,intend) { |
35 | | -while (start <end) { |
36 | | -chartemp =s[start]; |
37 | | -s[start++] =s[end]; |
38 | | -s[end--] =temp; |
39 | | - } |
| 30 | +publicstaticclassSolution2 { |
| 31 | +publicvoidreverseWords(char[]s) { |
| 32 | +reverse(s,0,s.length); |
| 33 | +for (inti =0;i <s.length;i++) { |
| 34 | +intstart =i; |
| 35 | +while (i <s.length &&s[i] !=' ') { |
| 36 | +i++; |
| 37 | + } |
| 38 | +reverse(s,start,i); |
| 39 | + } |
| 40 | + } |
| 41 | + |
| 42 | +privatevoidreverse(char[]chars,intstart,intend) { |
| 43 | +intleft =start; |
| 44 | +intright =end -1; |
| 45 | +while (left <right) { |
| 46 | +chartmp =chars[left]; |
| 47 | +chars[left] =chars[right]; |
| 48 | +chars[right] =tmp; |
| 49 | +left++; |
| 50 | +right--; |
| 51 | + } |
| 52 | + } |
40 | 53 | } |
41 | | - } |
42 | 54 |
|
43 | 55 | } |