LeetCode151.翻转字符串里的单词

待我称王封你为后i 2022-05-08 23:48 218阅读 0赞

给定一个字符串，逐个翻转字符串中的每个单词。

**示例:**

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

**说明:**

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

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

--------------------

思路：自己实现了一个函数将字符串拆分成不含空格以及不含空格字符串的字符串数组，最后再将返回的字符串数组由尾到头重新拼接。虽然也能通过，但是时间复杂度和空间复杂度比较高。

public class Solution {
        public String reverseWords(String s) {
             String res="";
            String str[]=spiltString(s);
            for(int i=str.length-1;i>0;i--){
                res+=str[i]+" ";
            }
            res+=str[0];
            return res;
        }
        /**
         * 将字符串拆分成字符串数组
         * @param str
         * @return
         */
        public  String[] spiltString(String str){
            List<String> list=new LinkedList<String>();
            str=str.trim();//去掉首尾空格
            char s[]=str.toCharArray();
            String tmpStr="";
            for(int i=0;i<s.length;i++){
                if(s[i]!=' '){
                    tmpStr+=s[i];
                }else{
                    list.add(tmpStr);
                    tmpStr="";//重新赋空串值
                    while (s[i]==' '){
                        i++;//直到s[i]不等于空格
                        if(i>=s.length){
                            break;
                        }
                    }
                    i--;//
                }
            }
            list.add(tmpStr);
            return list.toArray(new String[list.size()]);
        }
    }

在此，再分享一种耗时较少以及空间复杂度较低的一种算法。

public class Solution {
        public String reverseWords(String s) {
            s = s.trim();
            if(s.length()==0 || (!s.contains(" "))){
                return s;
            }
            String[] strings = s.split(" ");
            StringBuffer sb = new StringBuffer();
            for (int i = strings.length - 1; i >= 0; i--) {
                if(!strings[i].equals("")){
                    sb.append(strings[i]+" ");
                }
            }
    
            return  sb.toString().trim();
        }
    }