Leetcode 151. Reverse Words in a String

xiaoxiao2021-02-28  9

原题:

Given an input string, reverse the string word by word.

For example,Given s = "the sky is blue",return "blue is sky the".

Update (2015-02-12):For C programmers: Try to solve it in-place in O(1) space.

Clarification:

What constitutes a word?A sequence of non-space characters constitutes a word.Could the input string contain leading or trailing spaces?Yes. However, your reversed string should not contain leading or trailing spaces.How about multiple spaces between two words?Reduce them to a single space in the reversed string. 解决方法:

根据要求,基本思路是:先将整个字符串翻转,然后将每个单词翻转。

但是由于有额外的空格,我们需要写一个trim函数将所有的空格先删除掉。

代码: void reverse(string& s, int i, int j){ while(i < j) swap(s[i++], s[j--]); } void trim(string& s){ int n = s.size(), i = 0, j = n - 1; while(i <= j && s[i] == ' ') ++i; while(i <= j && s[j] == ' ') --j; int pos = 0; for(int k = i; k <= j; k++){ if (k != 0 && s[k] == ' ' && s[k] == s[k-1]) continue; s[pos++] = s[k]; } s.resize(pos); } void reverseWords(string &s) { trim(s); int n = s.size(); reverse(s, 0 , n-1); int i = 0; for(int j = 0 ; j < n;j++){ if (s[j] == ' ' || (j == n-1) ){ reverse(s, i, (j==n-1) ? j : (j - 1) ); i = j + 1; } } }
转载请注明原文地址: https://www.6miu.com/read-2150105.html

最新回复(0)