首页 > 代码库 > [LeetCode]Reverse Words in a String

[LeetCode]Reverse Words in a String

2024-07-04 04:51:42   226人阅读

题目：

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

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

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.

算法描述：

首先删除非法空格，包括前缀空格，后缀空格，以及冗余空格。为求效率，利用step计算需要搬移的步数，避免重复搬移。

其次两次reverse，完成题目。

时间复杂度O(n)，空间复杂度O(1)。

AC代码：

 1 class Solution {
 2 public:
 3     void _reverseWords(string &s, int left, int right){
 4         char tmp;
 5         for(int i = 0; i <= (right-left)/2; i++){
 6             tmp = s[left+i];
 7             s[left+i] = s[right-i];
 8             s[right-i] = tmp;
 9         }
10     }
11     
12     void reverseWords(string &s) {
13         int left = 0;
14         int right = 0;
15         int step = 0;
16         int length = s.length();
17         int deletespace = 1;
18         
19         for(int i = 0; i < length; i++){
20             if(s[i] == ‘ ‘){
21                 if(deletespace == 1){
22                     step++;
23                 }
24                 else
25                 {
26                     s[i - step] = s[i];
27                 }
28                 deletespace = 1;
29             }
30             else{
31                 deletespace = 0;
32                 s[i - step] = s[i];
33             }
34         }
35         
36         if(step != 0){
37             s.erase(length-step, step);
38         }
39         
40         if(s[s.length()-1] == ‘ ‘){
41             s.erase(s.length()-1, 1);
42         }
43         
44         _reverseWords(s, 0, s.length()-1);
45         
46         for(int i = 0; i< s.length(); i++){
47             if(s[i] == ‘ ‘){
48                 right = i - 1;
49                 _reverseWords(s, left, right);
50                 left = i + 1;
51             }
52         }
53         
54         _reverseWords(s, left, s.length()-1);
55     }
56 };

 


联系
我们