[Leetcode] Reverse Words in a String 反转单词顺序

codeKK 发布于2019-08-14 12:32 / 2132人阅读

摘要：代码先反转整个数组反转每个单词双指针交换法复杂度时间空间思路这题就是版的做法了，先反转整个数组，再对每个词反转。

Reverse Words in a String

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

使用API 复杂度

时间 O(N) 空间 O(N)

思路

将单词根据空格split开来存入一个字符串数组，然后将该数组反转即可。

注意

先用trim()将前后无用的空格去掉

用正则表达式" +"来匹配一个或多个空格

代码

public class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split(" +");
        int len = words.length;
        StringBuilder result = new StringBuilder();
        for(int i = len -1; i>=0;i--){
            result.append(words[i]);
            if(i!=0) result.append(" ");
        }
        return result.toString();
    }
}

双指针交换法 复杂度

时间 O(N) 空间 O(N) 如果输入时char数组则是O(1)

思路

先将字符串转换成char的数组，然后将整个数组反转。然后我们再对每一个单词多带带的反转一次，方法是用两个指针记录当前单词的起始位置和终止位置，遇到空格就进入下一个单词。

代码

public class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        char[] str = s.toCharArray();
        // 先反转整个数组
        reverse(str, 0, str.length - 1);
        int start = 0, end = 0;
        for(int i = 0; i < s.length(); i++){
            if(str[i]!=" "){
                end++;
            } else {
                // 反转每个单词
                reverse(str, start, end - 1);
                end++;
                start = end;
            }
        }
        return String.valueOf(str);
    }
    
    public void reverse(char[] str, int start, int end){
        while(start < end){
            char tmp = str[start];
            str[start] = str[end];
            str[end] = tmp;
            start++;
            end--;
        }
    }
}

Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example, Given s = "the sky is blue", return "blue is sky the". 
Could you do it in-place without allocating extra space?

双指针交换法 复杂度

时间 O(N) 空间 O(1)

思路

这题就是Java版的Inplace做法了，先反转整个数组，再对每个词反转。

代码

public class Solution {
    public void reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);
        int start = 0;
        for(int i = 0; i < s.length; i++){
            if(s[i] == " "){
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        reverse(s, start, s.length - 1);
    }
    
    public void reverse(char[] s, int start, int end){
        while(start < end){
            char tmp = s[start];
            s[start] = s[end];
            s[end] = tmp;
            start++;
            end--;
        }
    }
}

海外云主机服务器托管 LeetCode_String Aspose.Words Words Reverse

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64538.html

LeetCode 557：反转字符串中的单词 III Reverse Words in a Str

摘要：公众号爱写给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。示例输入输出注意在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。公众号：爱写bug（ID：icodebugs）给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。 Given a string, you need to revers...

CrazyCodes 2019-08-16 18:33 评论0 收藏0
LeetCode 557：反转字符串中的单词 III Reverse Words in a Str

摘要：公众号爱写给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。示例输入输出注意在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。公众号：爱写bug（ID：icodebugs）给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。 Given a string, you need to revers...

Zachary 2019-07-31 11:27 评论0 收藏0
LeetCode 之 JavaScript 解答第151题 —— 反转字符串中的单词

摘要：小鹿题目翻转字符串里的单词给定一个字符串，逐个翻转字符串中的每个单词。说明无空格字符构成一个单词。遇到空格之后，将单词进行倒序拼接。消除尾部的空格。测试用例空字符串。中间空格大于的字符串。 Time：2019/4/20Title: Reverse Words In a StringDifficulty: MidumnAuthor: 小鹿题目：Reverse Words In a ...

betacat 2019-08-23 17:05 评论0 收藏0
LeetCode 151：给定一个字符串，逐个翻转字符串中的每个单词 Reverse Words i

摘要：说明无空格字符构成一个单词。输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。我们将字符串转为字符型数组并用两个指针来解这道题。指针作为原字符串转为字符数组的索引，从右向左移。公众号：爱写bug（ID：icodebugs）翻转字符串里的单词 Given an input string, reverse the string word by word. 示例 1：...

red_bricks 2019-08-16 18:32 评论0 收藏0
LeetCode 151：给定一个字符串，逐个翻转字符串中的每个单词 Reverse Words i

摘要：说明无空格字符构成一个单词。输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。我们将字符串转为字符型数组并用两个指针来解这道题。指针作为原字符串转为字符数组的索引，从右向左移。公众号：爱写bug（ID：icodebugs）翻转字符串里的单词 Given an input string, reverse the string word by word. 示例 1：...

dongxiawu 2019-07-31 11:27 评论0 收藏0