?LeetCode刷題實(shí)戰(zhàn)151：翻轉(zhuǎn)字符串里的單詞
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
題意
無空格字符構(gòu)成一個(gè) 單詞 。
輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。
如果兩個(gè)單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)。
示例 1：
輸入："the sky is blue"
輸出："blue is sky the"
示例 2：
輸入：" ?hello world! ?"
輸出："world! hello"
解釋：輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。
示例 3：
輸入："a good ? example"
輸出："example good a"
解釋：如果兩個(gè)單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)。
示例 4：
輸入：s = " Bob Loves Alice "
輸出："Alice Loves Bob"
示例 5：
輸入：s = "Alice does not even like bob"
輸出："bob like even not does Alice"
解題
https://blog.csdn.net/weixin_43314519/article/details/107444407
方法一：使用語言特性
思路和算法
很多語言對(duì)字符串提供了?split（拆分），reverse（翻轉(zhuǎn)）和?join（連接）等方法，因此我們可以簡(jiǎn)單的調(diào)用內(nèi)置的 API 完成操作：
使用?
split?將字符串按空格分割成字符串?dāng)?shù)組；使用?
reverse?將字符串?dāng)?shù)組進(jìn)行反轉(zhuǎn)；使用?
join?方法將字符串?dāng)?shù)組拼成一個(gè)字符串。
class?Solution {
????public?String?reverseWords(String?s) {
????????// 除去開頭和末尾的空白字符
????????s = s.trim();
????????// 正則匹配連續(xù)的空白字符作為分隔符分割
????????List<String> wordList = Arrays.asList(s.split("\\s+"));
????????Collections.reverse(wordList);
????????return?String.join(" ", wordList);
????}
}
時(shí)間復(fù)雜度：O(N)，其中 N 為輸入字符串的長(zhǎng)度。
空間復(fù)雜度：O(N)，用來存儲(chǔ)字符串分割之后的結(jié)果。
方法二：自行編寫對(duì)應(yīng)的函數(shù)
class?Solution?{
????public?StringBuilder trimSpaces(String s)?{
????????int?left = 0, right = s.length() - 1;
????????// 去掉字符串開頭的空白字符
????????while?(left <= right && s.charAt(left) == ' ') ++left;
????????// 去掉字符串末尾的空白字符
????????while?(left <= right && s.charAt(right) == ' ') --right;
????????// 將字符串間多余的空白字符去除
????????StringBuilder sb = new?StringBuilder();
????????while?(left <= right) {
????????????char?c = s.charAt(left);
????????????if?(c != ' ') sb.append(c);
????????????else?if?(sb.charAt(sb.length() - 1) != ' ') sb.append(c);
????????????++left;
????????}
????????return?sb;
????}
????public?void?reverse(StringBuilder sb, int?left, int?right)?{
????????while?(left < right) {
????????????char?tmp = sb.charAt(left);
????????????sb.setCharAt(left++, sb.charAt(right));
????????????sb.setCharAt(right--, tmp);
????????}
????}
????public?void?reverseEachWord(StringBuilder sb)?{
????????int?n = sb.length();
????????int?start = 0, end = 0;
????????while?(start < n) {
????????????// 循環(huán)至單詞的末尾
????????????while?(end < n && sb.charAt(end) != ' ') ++end;
????????????// 翻轉(zhuǎn)單詞
????????????reverse(sb, start, end - 1);
????????????// 更新start，去找下一個(gè)單詞
????????????start = end + 1;
????????????++end;
????????}
????}
????public?String reverseWords(String s)?{
????????StringBuilder sb = trimSpaces(s);
????????// 翻轉(zhuǎn)字符串
????????reverse(sb, 0, sb.length() - 1);
????????// 翻轉(zhuǎn)每個(gè)單詞
????????reverseEachWord(sb);
????????return?sb.toString();
????}
}
時(shí)間復(fù)雜度：O(N)，其中 N 為輸入字符串的長(zhǎng)度。
空間復(fù)雜度：
Java?和?Python?的方法需要 O(N)O(N) 的空間來存儲(chǔ)字符串，而?C++?方法只需要?O(1)?的額外空間來存放若干變量。
方法三：雙端隊(duì)列
class?Solution?{
????public?String reverseWords(String s) {
????????int?left = 0, right = s.length() - 1;
????????// 去掉字符串開頭的空白字符
????????while?(left <= right && s.charAt(left) == ' ') ++left;
????????// 去掉字符串末尾的空白字符
????????while?(left <= right && s.charAt(right) == ' ') --right;
????????Dequed = new?ArrayDeque();
????????StringBuilder word = new?StringBuilder();
????????
????????while?(left <= right) {
????????????char?c = s.charAt(left);
????????????if?((word.length() != 0) && (c == ' ')) {
????????????????// 將單詞 push 到隊(duì)列的頭部
????????????????d.offerFirst(word.toString());
????????????????word.setLength(0);
????????????} else?if?(c != ' ') {
????????????????word.append(c);
????????????}
????????????++left;
????????}
????????d.offerFirst(word.toString());
????????return?String.join(" ", d);
????}
}
時(shí)間復(fù)雜度：O(N)，其中 N 為輸入字符串的長(zhǎng)度。
空間復(fù)雜度：O(N)，雙端隊(duì)列存儲(chǔ)單詞需要 O(N) 的空間。