专栏首页爱写BugLeetCode 151:给定一个字符串,逐个翻转字符串中的每个单词
原创

LeetCode 151:给定一个字符串,逐个翻转字符串中的每个单词

公众号:爱写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 计数。

Java:

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

Python3:

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]) # 剔除所有空格字符返回数组并反转,以空格为间隔把数组拼成字符串

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    爱写bug
  • LeetCode 557:反转字符串中的单词 III Reverse Words in a String III

    给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

    爱写bug
  • LeetCode 557:反转字符串中的单词 III Reverse Words in a String III

    给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

    爱写bug
  • LeetCode 151:给定一个字符串,逐个翻转字符串中的每个单词 Reverse Words in a String

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

    爱写bug
  • 6.3 字符数组

    1、对字符数组初始化,最容易理解的方式是用“初始化列表”,把各个字符依次赋给数组中各元素。

    C语言入门到精通
  • 6.3 C语言字符数组

    1、对字符数组初始化,最容易理解的方式是用“初始化列表”,把各个字符依次赋给数组中各元素。

    C语言入门到精通
  • 5.3 字符数组

    注意:用“”%s”格式符输入输出字符串时,printf函数中的输出项是字符数组名而不是数组元 素名

    C语言入门到精通
  • C++字符串结束的标志 | 用数组输出love

    在上面的字符数组中,第5个字符为′\0 ′,就表明字符串的有效字符为其前面的4个字符。也就是说,遇到字符′\0′就表示字符串到此结束,由它前面的字符组成字符串,...

    C语言入门到精通
  • C语言 | 将一个二维数组行列元素互换

    解题思路:可以定义两个数组:数组a为2行3列,存放指定的6个数。数组b为3行2列,开始时未赋值,只要将a数组中的元素ai存放到b数组中的bj元素中即可。

    C语言入门到精通
  • 《JavaScript语言精粹》学习笔记

    在JavaScript中,/ *可能出现在正则表达式字面量里,所以块注释对于被注释的代码块来说是<u>不安全的</u>。

    贺贺V5

扫码关注云+社区

领取腾讯云代金券