Reverse Words in a String

Tags: String, Medium

Question

Problem Statement

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.

题解

  1. 由第一个提问可知：题中只有空格字符和非空格字符之分，因此空格字符应为其一关键突破口。
  2. 由第二个提问可知：输入的前导空格或者尾随空格在反转后应去掉。
  3. 由第三个提问可知：两个单词间的多个空格字符应合并为一个或删除掉。

首先找到各个单词(以空格隔开)，根据题目要求，单词应从后往前依次放入。split 后从后往前加入空格返回即可。如果不使用 split 的话正向取出比较麻烦，因此可尝试采用逆向思维——先将输入字符串数组中的单词从后往前逆序取出，取出单词后即翻转并append至新字符串数组。在append之前加入空格即可，即两次翻转法。

Python

  1. class Solution(object):
  2.     def reverseWords(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: str
  6.         """
  7.         return ' '.join(reversed(s.strip().split()))

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param s : A string
  5.      * @return : A string
  6.      */
  7.     string reverseWords(string s) {
  8.         if (s.empty()) {
  9.             return s;
  10.         }
  12.         string s_ret, s_temp;
  13.         string::size_type ix = s.size();
  14.         while (ix != 0) {
  15.             s_temp.clear();
  16.             while (!isspace(s[--ix])) {
  17.                 s_temp.push_back(s[ix]);
  18.                 if (ix == 0) {
  19.                     break;
  20.                 }
  21.             }
  22.             if (!s_temp.empty()) {
  23.                 if (!s_ret.empty()) {
  24.                     s_ret.push_back(' ');
  25.                 }
  26.                 std::reverse(s_temp.begin(), s_temp.end());
  27.                 s_ret.append(s_temp);
  28.             }
  29.         }
  31.         return s_ret;
  32.     }
  33. };

Java

  1. public class Solution {
  2.     public String reverseWords(String s) {
  3.         if (s == null || s.trim().isEmpty()) {
  4.             return "";
  5.         }
  7.         String[] words = s.split(" ");
  8.         StringBuilder sb = new StringBuilder();
  9.         for (int i = words.length - 1; i >= 0; i--) {
  10.             if (!words[i].isEmpty()) {
  11.                 sb.append(words[i]).append(" ");
  12.             }
  13.         }
  15.         return sb.substring(0, sb.length() - 1);
  16.     }
  17. }

源码分析

  1. 首先处理异常，s 为空或者空白字符串时直接返回空。
  2. 如果首先排除掉空白字符串则后面不需要为长度为0单独考虑。
  3. Java 中使用 StringBuilder 效率更高。

空间复杂度为 O(1) 的解法？

  1. 处理异常及特殊情况
  2. 处理多个空格及首尾空格
  3. 记住单词的头尾指针，翻转之
  4. 整体翻转