101.Flip the word in the string_Intefrankly

101.Flip the word in the string

Title number 151.

Given a string, flip each word in the string one by one.

Example:

importation: "the sky is blue",

exports: "blue is sky the".

Description:

No space characters form a word.

The input string can be preceded or followed by extra spaces, but the inverted characters cannot be included.

If there are extra spaces between two words, reduce the spaces between the reversed words to contain only one.

Advanced: Users of the optional C language are invited to try the in-place solution using the O(1) space complexity.

Solution.

Disregarding spaces for the moment. Flip the words one by one, and finally flip the entire string once (a) The correct result will be obtained.

Consider spaces, use auxiliary space, space complexity O(n): traverse the string and skip if consecutive spaces are encountered, otherwise save the characters sequentially to the new string.

Optimization Thinking: How to deal with extra spaces during flipping if you don't use auxiliary spaces?

may Set a variable that points to the actual string (i.e. a string without extra spaces) Current position When extra spaces are encountered, the actual string position is left untouched, and the assignment continues forward only when non-space characters are encountered, with spaces between words.

Code implementation.

class Solution {

public:

void reverseWords(string &s) {

if(s.length()){

int j=0;

for(int i=0;i

while(i

i++;// skip space

}

int count=0;

if(j>0 && i

// Words need to be preceded by a space; (the space will follow the word when the whole string is flipped)

// no space before the first word (j==0); (the first word becomes the last after flipping the whole string, i.e. no space after the last word)

//i==s.length(), end of traversal

s[j++]=' ';

}

while(i

s[j++]=s[i++];

count++;

}

// Flip the words one by one

reverse(s.begin()+j-count,s.begin()+j);

}

// Removal of redundant characters

s.resize(j);

// Finally flip the entire string

reverse(s.begin(),s.end());

}

}

};

Recommended>>
1、On Taobao refinement operations how to maximize the benefits
2、Performance Analysis of FARCOM FCPROⅡ Multimedia Conference Room Central Control Host
3、The most important thing is that you have to be able to get the most out of your money
4、Share the Future is it a scam Revealed by Lee Anwar himself

已推荐到看一看 和朋友分享想法
最多200字，当前共 发送

已发送

确定
分享你的想法...
取消

确定
最多200字，当前共

发送中