【LeetCode】Reverse Words in a String 反转字符串中的单词

时间:2022-10-01 15:50:15

一年没有管理博客园了,说来实在惭愧。。

最近开始刷LeetCode,之前没刷过,说来也实在惭愧。。。

刚开始按 AC Rates 从简单到难刷,觉得略无聊,就决定按 Add Date 刷,以后也可能看心情随便选题…(⊙o⊙)…今天做了14年 Add 的三个题,其中 Maximum Product Subarray 着实把我折腾了好一会儿,所以想想还是跟大家分享一下我的解法,也或许有更好的方法,期待大家的分享。就把三个题按 Add Date 的先后顺序分享一下吧。

Add Date 2014-03-05

Reverse Words in a String

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.

单纯把 "the sky is blue" reverse 成 "blue is sky the" 是件很容易的事情,也是比较经典的题目,不过本题说:

1. s 中的开头和结尾有可能有空格,reverse 后的 string 中要去掉;

2. 连续多个空格要变成一个空格。

我的 code 略折腾,用了两个函数:

1. reverseWord 实现最基本的 reverse,首先整个 reverse,变为“eulb si yks eht”,然后每个 word reverse,遍历两边即可。

2. removeSpace 实现检查和删除空格。遍历一遍即可。

复杂度O(n).

附 code,仅供参考。

【LeetCode】Reverse Words in a String 反转字符串中的单词【LeetCode】Reverse Words in a String 反转字符串中的单词
 1 class Solution {
 2 public:
 3     void reverseWord(string &s) {                       //反转字符串
 4         string::iterator pre = s.begin();
 5         string::iterator post = s.end()-1;
 6         char tmp;
 7         while(pre < post) {                             //反转整个字符串
 8             tmp = *pre;
 9             *pre = *post;
10             *post = tmp;
11             ++pre;
12             --post;
13         }
14         pre = s.begin();
15         post = pre;
16         while(post != s.end()) {                        //反转每个单词
17             while(pre != s.end() && *pre == ' ') {
18                 ++pre;
19             }
20             if(pre == s.end())
21                 return;
22             post = pre;
23             while(post != s.end() && *post != ' ') {
24                 ++post;
25             }
26             --post;
27             if(post != s.end() && pre < post) {
28                 string::iterator p1 = pre;
29                 string::iterator p2 = post;
30                 while(p1 < p2) {
31                     tmp = *p1;
32                     *p1 = *p2;
33                     *p2 = tmp;
34                     ++p1;
35                     --p2;
36                 }
37             }
38             ++post;
39             pre = post;
40         }
41     }
42     
43     void removeSpace(string &s) {                       //检查和删除空格
44         string::iterator pre = s.begin();
45         string::iterator post = pre;
46         while(pre != s.end() && *pre == ' ') {          //删除开头的空格
47             s.erase(s.begin());
48             pre = s.begin();
49         }
50         if(pre == s.end())
51             return;
52         post = pre;
53         while(post != s.end()) {                        //把连续多个空格变为一个
54             while(pre != s.end() && *pre != ' ')
55                 ++pre;
56             if(pre == s.end())
57                 return;
58             post = pre+1;
59             while(post != s.end() && *post == ' ') {
60                 s.erase(post);
61                 post = pre+1;
62             }
63             ++pre;
64         }
65         if(!s.empty()) {                                //如果最后有空格则删除
66             pre = s.end()-1;
67             if(*pre == ' ')
68                 s.erase(pre);
69         }
70     }
71     
72     void reverseWords(string &s) {
73         reverseWord(s);
74         removeSpace(s);
75     }
76 };
View Code