leetcode【字符串—中等】151.翻转字符串里的单词

文章目录

• 前言
• 题目
• 题解
• NO1：拼接法
• 优化前(Stringbuilder拼接)
• 优化后(char[]，时间复杂度最优解)
• No2：双反转+移位
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为字符串专题。

---

题目

题目来源leetcode

leetcode地址：151. 翻转字符串里的单词，难度：中等。

题目描述(摘自leetcode)：

给你一个字符串 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 中 至少存在一个 单词

本地调试代码：

class Solution {
    public int search(int[] nums, int target) {
        ....
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{-1,0,3,5,9,12};//这里修改数组内容
        System.out.println(solution.search(arr, 2));//数组、目标值
    }
}

---

题解

NO1：拼接法

优化前(Stringbuilder拼接)

思路：从前往后进行遍历，遇到空格往后移动一步，遇到非空格先记录下当前索引，接着一直遍历到该单词的后一个位置，取出该单词最终进行拼接返回。

代码：

//"the sky is blue" => "blue is sky the"
public String reverseWords(String s) {
    StringBuilder str = new StringBuilder();
    int i = 0;
    //遍历字符串结束
    while(i<s.length()){
        //过滤空字符串
        while(i<s.length() && s.charAt(i) == ' '){i++;}
        if( i == s.length()){
            break;
        }
        int temp = i;
        while(i<s.length() && s.charAt(i) != ' '){i++;}
        String word =  s.substring(temp,i);
        str = new StringBuilder(word).append(" ").append(str);
    }
    if(str.length()>0){
        return str.substring(0,str.length() - 1);
    }
    return "";
}

这里直接使用了String的api来进行截取字符串操作，并且来进行合并多个单词时频繁创建StringBuilder，不仅仅影响时间还有空间复杂度。

---

优化后(char[]，时间复杂度最优解)

思路：这里是从后往前进行遍历，首先遇到!=空格的先记录索引left，紧接着继续向前移动直到为邻接点或者=空格停止，此时我们就能够拿到对应单词的范围索引，将该单词取出依次存储到新字符数组中。

代码：时间复杂度O(n)、空间复杂度O(n)

• 这里是没有任何API进行调用的，纯对字符数组进行操作，所以比优化前的效果好很多

public String reverseWords(String s) {
    //源字符数组
    char[] initialArr = s.toCharArray();
    //新字符数组
    char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 "，最终末尾的空格不会返回
    int newArrPos = 0;
    //i来进行整体对源字符数组从后往前遍历
    int i = initialArr.length-1;
    while(i>=0){
        while(i>=0 && initialArr[i] == ' '){i--;}  //跳过空格
        //此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置
        int right = i;
        while(i>=0 && initialArr[i] != ' '){i--;} 
        //指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格
        for (int j = i+1; j <= right; j++) {
            newArr[newArrPos++] = initialArr[j];
            if(j == right){
                newArr[newArrPos++] = ' ';//空格
            }
        }
    }
    //若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
    if(newArrPos == 0){
        return "";
    }else{
        return new String(newArr,0,newArrPos-1);
    }
}

---

No2：双反转+移位

思路：并没有开辟新的数组或字符串来进行拼接，而是在原始字符数组上来进行操作。

①反转字符串 "the sky is blue "=> " eulb si yks eht"

②遍历" eulb si yks eht"，过程中先对某个单词进行反转再移位

• 对第一个单词进行操作举例：" eulb si yks eht" =反转> " blue si yks eht" =移位> "blue si yks eht"

代码：时间复杂度O(n)、空间复杂度O(1)

/**
  * 空间复杂度O(1)解法
  */
public String reverseWords(String s) {
    //步骤1：字符串整体反转（此时其中的单词也都反转了）
    char[] initialArr = s.toCharArray();
    reverse(initialArr, 0, s.length() - 1);
    int k = 0;
    for (int i = 0; i < initialArr.length; i++) {
        if (initialArr[i] == ' ') {
            continue;
        }
        int tempCur = i;
        while (i < initialArr.length && initialArr[i] != ' ') {
            i++;
        }
        for (int j = tempCur; j < i; j++) {
            if (j == tempCur) { //步骤二：二次反转
                reverse(initialArr, tempCur, i - 1);//对指定范围字符串进行反转，不反转从后往前遍历一个个填充有问题
            }
            //步骤三：移动操作
            initialArr[k++] = initialArr[j];
            if (j == i - 1) { //遍历结束
                //避免越界情况，例如=> "asdasd df f"，不加判断最后就会数组越界
                if (k < initialArr.length) {
                    initialArr[k++] = ' ';
                }
            }
        }
    }
    if (k == 0) {
        return "";
    } else {
        //参数三：以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
        return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
    }
}

public void reverse(char[] chars, int begin, int end) {
    for (int i = begin, j = end; i < j; i++, j--) {
        chars[i] ^= chars[j];
        chars[j] ^= chars[i];
        chars[i] ^= chars[j];
    }
}

---

参考文章

[1]. leetcode题解

[2]. 代码随想录—151.翻转字符串里的单词

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.10.23