65 lines
1.5 KiB
C++
65 lines
1.5 KiB
C++
|
// Source : https://oj.leetcode.com/problems/reverse-words-in-a-string-ii/
|
||
|
|
// Author : Hao Chen
|
||
|
|
// Date : 2015-02-09
|
||
|
|
|
||
|
|
/**********************************************************************************
|
||
|
|
*
|
||
|
|
* 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?
|
||
|
|
*
|
||
|
|
*
|
||
|
|
**********************************************************************************/
|
||
|
|
|
||
|
|
#include <ctype.h>
|
||
|
|
#include <iostream>
|
||
|
|
#include <string>
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
|
||
|
|
void swap(char &a, char &b) {
|
||
|
|
char temp = a;
|
||
|
|
a = b;
|
||
|
|
b = temp;
|
||
|
|
}
|
||
|
|
void reverse(string &s, int begin, int end) {
|
||
|
|
while(begin < end) {
|
||
|
|
swap(s[begin++], s[end--]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
void reverseWords(string &s) {
|
||
|
|
|
||
|
|
if (s.size()<=1) return;
|
||
|
|
|
||
|
|
// reverse the whole string
|
||
|
|
reverse(s, 0, s.size()-1);
|
||
|
|
|
||
|
|
// reverse the each word
|
||
|
|
for ( int begin=0, i=0; i<=s.size(); i++ ) {
|
||
|
|
if ( isblank(s[i]) || s[i] == '\0') {
|
||
|
|
reverse(s, begin, i-1);
|
||
|
|
begin = i+1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
int main(int argc, char** argv)
|
||
|
|
{
|
||
|
|
string s = "the sky is blue";
|
||
|
|
if ( argc > 1 ) {
|
||
|
|
s = argv[1];
|
||
|
|
}
|
||
|
|
|
||
|
|
cout << s << endl;
|
||
|
|
reverseWords(s);
|
||
|
|
cout << s << endl;
|
||
|
|
|
||
|
|
}
|