-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrevese_word_in_string.cpp
More file actions
66 lines (59 loc) · 1.67 KB
/
revese_word_in_string.cpp
File metadata and controls
66 lines (59 loc) · 1.67 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
lettcode] 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".
*/
class Solution {
public:
void reverseWords(string &s) {
int i = 0, j = 0, k = 0, wordCount = 0;
while (true) {
while (i < s.size() && s[i] == ' ') ++i;
if (i == s.size()) break;
if (wordCount) s[j++] = ' ';
k = j;
while (i < s.size() && s[i] != ' ') {
s[j] = s[i];
++j; ++i;
}
reverseWord(s, k, j - 1);
++wordCount;
}
s.resize(j);
reverseWord(s, 0, j - 1);
}
void reverseWord(string &s, int i, int j) {
while (i < j) {
swap(s[i++],s[j--]);
}
}
};
/*
[LeetCode] 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?
*/
class Solution {
public:
void reverseWords(string &s) {
int left = 0;
for (int i = 0; i <= s.size(); ++i) {
if (i == s.size() || s[i] == ' ') {
reverse(s, left, i - 1);
left = i + 1;
}
}
reverse(s, 0, s.size() - 1);
}
void reverse(string &s, int left, int right) {
while (left < right) {
swap(s[left++], s[right--]);
}
}
};