151. Reverse Words in a String翻转一句话中的单词

时间:2021-10-05 13:53:21

[抄题]:

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

Example:  

Input: "the sky is blue",
Output: "blue is sky the".

 [暴力解法]:

时间分析:

空间分析:

 [优化后]:

时间分析:

空间分析:

[奇葩输出条件]:

[奇葩corner case]:

[思维问题]:

打碎成数组后再添加,居然有看不懂的bug。

 

151. Reverse Words in a String翻转一句话中的单词151. Reverse Words in a String翻转一句话中的单词
public class Solution {
    public String reverseWords(String s) {
        //ini
        char[] str = s.toCharArray();
        
        //cc
        if (str == null || str.length == 0) return s;
        
        //3 step3: reverse the whole, word, last
        reverse(str, 0, str.length - 1);
        
        int wordStart = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == ' ') {
                reverse(str, wordStart, i - 1);
                wordStart = i + 1;
            }
        }
        
        reverse(str, wordStart, str.length - 1);
    
    
    private void reverse(char[] str, int start, int end) {
        //do in a while loop
        while (start < end) {
            char temp = str[start];
            str[start] = str[end];
            str[end] = temp;
            
            start++;
            end--;
        }
    }
        
        //return 
        StringBuilder sb = new StringBuilder();
        for (char ch : str) sb.append(ch);
        
        return sb.toString();
    }
}
View Code

 

[英文数据结构或算法,为什么不用别的数据结构或算法]:

[一句话思路]:

.split("\\s+")把单词分开(特别注意是反斜杠),然后倒贴(单词+空格),最后一个单词不贴空格。

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

[一刷]:

反斜杠写成正斜杠就错了

[二刷]:

[三刷]:

[四刷]:

[五刷]:

  [五分钟肉眼debug的结果]:

[总结]:

不管输入是字符串还是字符数组,最后一个单词都先不贴,因为后面没有空格

[复杂度]:Time complexity: O(n) Space complexity: O(n)

[算法思想:迭代/递归/分治/贪心]:

[关键模板化代码]:

[其他解法]:

[Follow Up]:

[LC给出的题目变变变]:

 [代码风格] :

 [是否头一次写此类driver funcion的代码] :

 [潜台词] :

 

151. Reverse Words in a String翻转一句话中的单词151. Reverse Words in a String翻转一句话中的单词
public class Solution {
    public String reverseWords(String s) {
        //ini
        String result = new String();
        s = s.trim();
        
        //cc
        if (s == null || s.length() == 0) return result;
        
        //split into words
        String[] words = s.split("\\s+");
        
        //append for n - 1 to 1
        for (int i = words.length - 1; i > 0; i--)
            result += words[i] + " ";
        
        //append 0
        result += words[0];
        
        //return
        return result;
    }
}
View Code