151. 翻轉(zhuǎn)字符串里的單詞
方法一：雙指針
算法解析：
- 倒序遍歷字符串
s棚愤，記錄單詞左右索引邊界i,j搓萧； - 每確定一個單詞的邊界，則將其添加至單詞列表
res宛畦； - 最終，將單詞列表拼接為字符串揍移，并返回即可次和。
復雜度分析：
- 時間復雜度 O(N)： 其中
N為字符串s的長度，線性遍歷字符串那伐。 - 空間復雜度 O(N) ： 新建的 list(Python) 或 StringBuilder(Java) 中的字符串總長度 ≤N 踏施，占用 O(N)大小的額外空間石蔗。
Screen Shot 2020-04-11 at 01.28.00.png
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 刪除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while(i >= 0) {
while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首個空格
//注意上面是從j - 1開始遍歷，所以在這里是j + 1
res.append(s.substring(i + 1, j + 1) + " "); // 添加單詞
while(i >= 0 && s.charAt(i) == ' ') i--; // 跳過單詞間空格
j = i; // j 指向下個單詞的尾字符
}
return res.toString().trim(); // 轉(zhuǎn)化為字符串并返回
}
}
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" ");
StringBuilder res = new StringBuilder();
for (int i = strs.length - 1; i >=0; i--) {
if (strs[i].equals("")) continue;
res.append(strs[i] + " ");
}
return res.toString().trim();
}
}
