LeetCode-151给定一个字符串逐个翻转字符串中的每个单词-Reverse-Words-in-a-String

jiezi

5 年前

公众号：爱写 bug（ID：icodebugs）

翻转字符串里的单词

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

示例 1：

 输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

 输入: "hello world!"
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

 输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

Note:

A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

Java 字符串不支持运算符重载，无法用原地解法。我们将字符串转为字符型数组并用两个指针来解这道题。指针 i 作为原字符串转为字符数组的索引，从右向左移。指针 j 作为新字符数组索引，从左向右赋值得到原数组 count 长度的字符。count 记录遇到的字母数量，每次遇到空格字符，新数组得到从该空格字符向右 count 个字符并刷新 count 计数。

class Solution {public String reverseWords(String s) {if (s.length()==0)return s;// 如果为空直接返回
        char strs[]=s.toCharArray(),ans[]=new char[s.length()];// 字符串转为 char 字符数组
        int count=0,j=0;// 全局变量 j 记录新数组索引
        for(int i=s.length()-1;i>=0;i--){ 指针 i 从右向左遍历 strs 字符
            if(strs[i]==' '){// 判断是否为空格字符
                int k=i+1;
                if(count>0){while (--count>=0){// 从字符 i 向右 count 个字符赋给新数组 ans
                        ans[j++]=strs[k++];
                    }
                    ans[j++]=' ';
                    count=0;//count 初始化为 0
                }
            }else if(i==0){for(;i<=count;i++)ans[j++]=strs[i];// 左移到第一个字符时证明不是以空格开头，则从 0 获取 count+ 1 个个字符赋给 ans
                j+=1;
                break;
            }
            else {count++;// 如果是字母，则 count 累加 1}
        }
        if(j<1)return "";// 如果 j 依然是 0，则原字符串全为空格，返回空字符串
        String string=String.valueOf(ans,0,j-1);//char 数组转为字符串返回
        return string;
    }
}

为了考虑性能，转成了多个判断，所以有些繁琐。最终运行：Your runtime beats 99.91 % of java submissions

python 完全可以实现 Java 的思路，不再复现。这里利用函数投机取巧：

split()，它可以把传入字符串剔除空格后返回所有单词的数组

join()，它可以指定一个数组以特定字符为间隔，拼接成一个字符串

加上 [::-1] 反转数组，一行代码既可实现该题目要求

‘ abc def ‘ 原字符串

[‘abc’ , ‘def’] 剔除空格返回 String 型单词数组

[‘def’ , ‘abc’] 切片反转数组

‘def abc’ 拼接成字符串

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(s.split()[::-1]) # 剔除所有空格字符返回数组并反转，以空格为间隔把数组拼成字符串

LeetCode-151给定一个字符串逐个翻转字符串中的每个单词-Reverse-Words-in-a-String

解题思路：

Java：

Python3：