题目
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入："the sky is blue" 输出："blue is sky the"
示例 2：
输入：" hello world! " 输出："world! hello" 解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入："a good example" 输出："example good a" 解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例 4：
输入：s = " Bob Loves Alice " 输出："Alice Loves Bob"
示例 5：
输入：s = "Alice does not even like bob" 输出："bob like even not does Alice"
解题
方法一：使用语言特性
很多语言对字符串提供了 split（拆分），reverse（翻转）和 join（连接）等方法，因此我们可以简单的调用内置的 API 完成操作：
class Solution: def reverseWords(self, s: str) -> str: return " ".join(reversed(s.split()))
注意
这样子是不行的，因为这样只是以空格split,但是如果单词之间出现2个空格，就没有办法了。
split()默认是以空格、退格、回车等作为分隔.
return " ".join(reversed(s.split(" ")))
方法二：双端队列
class Solution: def reverseWords(self, s: str) -> str: left, right = 0, len(s) - 1 # 去掉字符串开头的空白字符 while left <= right and s[left] == ' ': left += 1 # 去掉字符串末尾的空白字符 while left <= right and s[right] == ' ': right -= 1 d, word = collections.deque(), [] # 将单词 push 到队列的头部 while left <= right: # 一定要取等号，不然最后一个字符取不到 if s[left] == ' ' and word: d.appendleft(''.join(word)) word = [] elif s[left] != ' ': word.append(s[left]) left += 1 d.appendleft(''.join(word)) return ' '.join(d)
方法三：c++解法1
class Solution { public: string reverseWords(string s) { int len = s.length(), i = 0; string ans = "", tmp; while(i < len){ tmp = ""; while(i < len && s[i] == ' ') i++; while(i < len && s[i] != ' ') tmp += s[i++]; if(tmp != ""){ //防止s末尾的空格 ans = tmp + " " + ans; } } return ans.substr(0, ans.length()-1); } };
substr相当于python中对字符串的切片
最后ans.substr(0, ans.length()-1);是为了舍弃字符串最后一个字符
因为刚开始进入ans = tmp + " " + ans;时候，ans="",直接 tmp+空格,所以末尾会多一个空格,最后return的时候空格是出现在最末尾.
方法四：c++解法2
class Solution { public: // 反转字符串s中左闭又闭的区间[start, end] void reverse(string& s, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { swap(s[i], s[j]); } } // 移除冗余空格：使用双指针（快慢指针法）O(n)的算法 void removeExtraSpaces(string& s) { int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针 // 去掉字符串前面的空格 while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') { fastIndex++; } for (; fastIndex < s.size(); fastIndex++) { // 去掉字符串中间部分的冗余空格 if (fastIndex - 1 > 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') { continue; } else { s[slowIndex++] = s[fastIndex]; } } if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格 s.resize(slowIndex - 1); } else { s.resize(slowIndex); // 重新设置字符串大小 } } string reverseWords(string s) { removeExtraSpaces(s); // 去掉冗余空格 reverse(s, 0, s.size() - 1); // 将字符串全部反转 int start = 0; // 反转的单词在字符串里起始位置 int end = 0; // 反转的单词在字符串里终止位置 bool entry = false; // 标记枚举字符串的过程中是否已经进入了单词区间 for (int i = 0; i < s.size(); i++) { // 开始反转单词 if (!entry) { start = i; // 确定单词起始位置 entry = true; // 进入单词区间 } // 单词后面有空格的情况，空格就是分词符 if (entry && s[i] == ' ' && s[i - 1] != ' ') { end = i - 1; // 确定单词终止位置 entry = false; // 结束单词区间 reverse(s, start, end); } // 最后一个结尾单词之后没有空格的情况 if (entry && (i == (s.size() - 1)) && s[i] != ' ' ) { end = i;// 确定单词终止位置 entry = false; // 结束单词区间 reverse(s, start, end); } } return s; } // 当然这里的主函数reverseWords写的有一些冗余的，可以精简一些，精简之后的主函数为： /* 主函数简单写法 string reverseWords(string s) { removeExtraSpaces(s); reverse(s, 0, s.size() - 1); for(int i = 0; i < s.size(); i++) { int j = i; // 查找单词间的空格，翻转单词 while(j < s.size() && s[j] != ' ') j++; reverse(s, i, j - 1); i = j; } return s; } */ };
方法五：c++解法3
class Solution { public: string reverseWords(string s) { int n=s.size(); int left=0; int right=n-1; while(left<n&&s[left]==' ') left++; while(right>=0&&s[right]==' ') right--; string res=""; while(right>=left){ int start=right; while(right>=left&&s[right]!=' ') right--; res+=s.substr(right+1,start-right); while(right>=left&&s[right]==' ') right--; if(right!=left-1){ res+=" "; } } return res; } };
java
class Solution { public String reverseWords(String s) { int n=s.length(); StringBuilder res=new StringBuilder(); //两边去掉空格 int left=0,right=n-1; while(right>=0&&s.charAt(right)==' ') right--; while(left<n&&s.charAt(left)==' ') left++; while(left<=right){ int start=right; while(right>=left&&s.charAt(right)!=' ') right--; res.append(s.substring(right+1,start+1)); while(right>=left&&s.charAt(right)==' ')right--;//跳过空格 if(right!=left-1){ res.append(' '); } } return res.toString(); }
或者使用java提供的一些函数
class Solution { public String reverseWords(String s) { String[] str=s.split(" "); StringBuilder sb=new StringBuilder(); int state=0; for(int i=str.length-1;i>=0;i--){ if(!str[i].equals("")){//注意是空的，因为连续两个空格split的话，" "得到结果为{"","",""} sb.append(str[i]); sb.append(" "); } } return sb.toString().trim(); } }
