A nice two pointer problem

Blabla before diving into the question

Basic idea

  1. Reverse the whole string
  2. Reverse each word
  3. Remove extra space
  • if we have a space, we reset left and right to next location.
  • If not a space, we increase right pointer
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i = 0;
for (int j = 0; j < nums.size(); ++j)
if (nums[j])swap(nums[i++], nums[j]);
}
};

Reference Code

class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end());
s.push_back(' ');
// reverse each word
int left = 0, right = 0;
for (int i = 0; i < s.size(); ++i){
if (s[i] == ' '){
reverse(s.begin() + left, s.begin() + right);
left = i + 1; right = i + 1;
} else {
right++;
}
}
// remove the extra space
left = 0;
for (int i = 0; i < s.size(); ++i){
if (s[i] != ' '){
swap(s[i], s[left++]);
if (s[i+1] == ' ')left++;
}
}
s.erase(s.begin() + left - 1, s.end());
return s;
}
};

Reference

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store