Friday, December 5, 2014

reverse words in a sentence (C++)-- Leetcode

Question:


Answer:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

void reverseStr(string &s, int i, int j){
char temp;
while(i<j){
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}

void reverseWords(string &s) {
if(s.length() == 0) return;
reverseStr(s, 0, s.size()-1);          //Reverse the whole string firstly.
int i = 0, count = 0;
while(s[i]==' '){
i++;
count++;
}

int begin = i-count;
while(i <= s.length()-1){
//cout <<"Debug: |" << s.substr(i) << endl;
if(s[i] == ' '){              //For s[i] == first ' ' after a word end, shift count num.
s[i-count] = s[i];
reverseStr(s, begin, i-count-1);

while(s[i+1] == ' '){
i++;
count++;
}
begin = i+1-count;
}
else if(i == s.length()-1){       //For last word end without ' 'next reversing!!!Important!
s[i-count] = s[i];
reverseStr(s, begin, i-count);
}
else{
s[i-count] = s[i];          //For s[i] is a valid word char, shift count num.
}
i++;
}
for(int i=0;i<count;++i){
s.pop_back();
}
if(s[s.length()-1] == ' ') s.pop_back();
}

int main(int argc, char** argv){
string str = "  abc   def  eghi  ";
cout << str << endl;
reverseWords(str);
cout << str;
getchar();
return 0;
}