-
Notifications
You must be signed in to change notification settings - Fork 0
/
ReverseStringWords.cpp
66 lines (57 loc) · 2.35 KB
/
ReverseStringWords.cpp
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
/*
* Laurie Kirk 8-9-20
* Reversing the words in a string
* Space comlexity: O(1)
* Time complexity: O(n) where n is the number of characters in the input string
*/
class Solution {
public:
string reverseWords(string s) {
int left_index = 0; // Front of the string
int right_index = s.size() - 1; // Back of the string
int temp_index = -1;
int last_word = false;
// Account for the empty string or only whitespace
if (s.compare("") == 0 || s.find_first_not_of(' ') == std::string::npos)
return "";
// Keep reversing until we reach the word that was first
while (!last_word)
{
// Find next word removing any whitespace
while (std::isspace(s[right_index]) || std::isspace(s[left_index]))
{
if (std::isspace(s[right_index]))
{
s.erase(s.begin() + right_index);
--right_index;
}
if (std::isspace(s[left_index]))
{
s.erase(s.begin() + left_index);
// Account for shift
--right_index;
}
}
// Now we should be at the next word so we find its beginning
temp_index = right_index;
while (temp_index - 1 >= 0 && !std::isspace(s[temp_index-1]))
--temp_index;
// If we haven't reached the first word which should now be in its correct place
if (temp_index - 1 >= 0 && temp_index > left_index)
{
// Copy word to the left index and remove the right one
s.insert(left_index, s.substr(temp_index, right_index - temp_index + 1) + " ");
// Account for the extra letters at the beginning
s.erase(s.begin() + temp_index + (right_index - temp_index + 1), s.end());
// Set the left index to the next location to insert at
// Note: +2 because we are accounting for the extra space
left_index += right_index - temp_index + 2;
} else
{
// Set our loop breaking flag
last_word = true;
}
}
return s;
}
};