剑指Offer 44. 反转字符串中的单词
题目描述
方法一：使用正则表达式分割字符串
1 class Solution {2 public String reverseWords(String s) {3 if(s == null || s.trim().length() == 0){4 return "";5 }6 // 用正则表达式分割成数组，处理多个空格7 String[] splits = s.trim().split("\s+");8 // 使用StringBuilder进行拼接9 StringBuilder sb = new StringBuilder();10 for(int i = splits.length - 1; i >= 0; i--){11 sb.append(splits[i]);12 if(i > 0){13 sb.append(" ");14 }15 }16 return sb.toString();17 }18 }
LeetCode运行时间：8 ms - 16.63%，空间：39.3 MB - 14.95%
复杂度分析：
时间复杂度：split()函数的时间复杂度为O(n)，遍历数组的时间复杂度为O(n)，总的时间复杂度为O(n)。
空间复杂度：需要一个额外的数组来存放单词，因此空间复杂度为O(n)。使用栈实现倒序会增加一个O(n)的空间复杂度。
方法二：使用空格分割字符串并过滤空串
使用split()函数分割字符串时仍使用空格，但在拼接结果字符串时需判断是否为空串，是则跳过。
1 class Solution {2 public String reverseWords(String s) {3 if(s == null || s.trim().length() == 0){4 return "";5 }6 // 用空格分割成数组7 String[] splits = s.trim().split(" ");8 // 使用StringBuilder进行拼接9 StringBuilder sb = new StringBuilder();10 for(int i = splits.length - 1; i >= 0; i--){11 if("".equals(splits[i])){12 continue;13 }14 sb.append(splits[i]);15 if(i > 0){16 sb.append(" ");17 }18 }19 return sb.toString();20 }21 }
复杂度分析：
时间复杂度：split()函数的时间复杂度为O(n)，遍历数组的时间复杂度为O(n)，总的时间复杂度为O(n)。
空间复杂度：需要一个额外的数组来存放单词，因此空间复杂度为O(n)。使用栈实现倒序会增加一个O(n)的空间复杂度。
方法三：双指针法
不使用split()函数，从后往前遍历字符串，获取单词并添加到结果字符串中。
1 class Solution {2 public String reverseWords(String s) {3 if(s == null || s.trim().length() == 0){4 return "";5 }6 s = s.trim();7 // 两个指针，i 和 j，初始时都在末尾8 int i = s.length() - 1, j = i;9 StringBuilder sb = new StringBuilder();10 while(i >= 0){11 // 让i指针向前查找，直到遇到第一个空格12 while(i >= 0 && s.charAt(i) != ' '){13 i--;14 }15 // 截取[i+1, j+1)的子串到sb16 sb.append(s.substring(i+1, j+1) + " ");17 // 跳过单词间的多余空格18 while(i >= 0 && s.charAt(i) == ' '){19 i--;20 }21 j = i;22 }23 return sb.toString().trim();24 }25 }
复杂度分析：
参考来源：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/solution/mian-shi-ti-58-i-fan-zhuan-dan-ci-shun-xu-shuang-z/
京公网安备 11010802041100号