151. 翻转字符串里的单词

题目地址(151. 翻转字符串里的单词)

https://leetcode-cn.com/problems/reverse-words-in-a-string/

题目描述

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
示例 3：
输入：s = "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"
提示：
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
进阶：
请尝试使用 O(1) 额外空间复杂度的原地解法。

前置知识

公司

• 暂无

思路

将整个字符串倒过来 然后再把单个单词倒过来
解题思路如下：

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

举个例子，源字符串为：”the sky is blue “

• 移除多余空格 : “the sky is blue”
• 字符串反转：”eulb si yks eht”
• 单词反转：”blue is sky the”

本题使用的是双指针来解决问题
翻转字符串 类似 344翻转字符串

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
        public String reverseWords(String s) {
            //1. 清除多余空格
            StringBuilder sb = removeSpace(s);
            //2. 翻转整个字符串
            reverseString(sb, 0, sb.length()-1);
            //3. 翻转每个单词
            reverseEachWord(sb);
            return sb.toString();
        }
        private StringBuilder removeSpace(String s) {
            StringBuilder sb = new StringBuilder();
            int left = 0;
            int right = s.length() - 1;
            //去除两端空格
            while (s.charAt(left) == ' ') {
                left++;
            }
            while (s.charAt(right) == ' ') {
                right--;
            }
            //去除中间多余空格
            while (left <= right) {
                char charA = s.charAt(left);
                //如果charA!=空格 就把字符添加到sb中 或者当前sb最后一个不是空格 就把空格添加到里面
                if (charA != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                    sb.append(charA);
                }
                left++;
            }
            return sb;
        }
        private void reverseString(StringBuilder sb, int left, int right) {
            while (left < right) {
                //翻转整个数组
                char temp = sb.charAt(left);
                sb.setCharAt(left, sb.charAt(right));
                sb.setCharAt(right, temp);
                left++;
                right--;
            }
        }
        private void reverseEachWord(StringBuilder sb) {
            int left = 0;
            int right = 1;
            int size = sb.length();
            while (left < size) {
                //将当前的right移动到当前单词的末尾
                while (right < size && sb.charAt(right) != ' ') {
                    right++;
                }
                //翻转单个单词
                reverseString(sb, left, right-1);
                //当前左端移到空格右边一格 右端移到当前左端的右边
                left = right+1;
                right = left +1;
            }
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=Nrbd1)
• 空间复杂度：#card=math&code=O%28n%29&id=F9z5d)