557. 反转字符串中的单词 III
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
提示：
在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
方法1：使用自带的 split 和 reverse 函数
参考代码1:
class Solution {
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return s;
}
String[] strs = s.split(" ");
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(new StringBuilder(str).reverse() + " ");
}
return sb.toString().trim();
}
}
复杂度分析：
- 时间复杂度：O(n)。其中 n 是字符串的长度。
- 空间复杂度：O(n)。使用了大小为 n 的 StringBuilder 空间。
方法2：不使用自带的 split 和 reverse 函数
算法思路：
我们自己写一个 split 和 reverse 函数。 split 函数将字符串 " " (空格)为分隔符将字符串分开并返回单词列表。 reverse 函数返回每个字符串反转后的字符串。
参考代码2:
class Solution {
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return s;
}
String[] strs = split(s);
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(reverse(str) + " ");
}
return sb.toString().trim();
}
private String[] split(String s) {
List<String> words = new ArrayList<>();
StringBuilder word = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ') {
words.add(word.toString());
word = new StringBuilder();
} else {
word.append(s.charAt(i));
}
}
words.add(word.toString());
return words.toArray(new String[words.size()]);
}
private String reverse(String s) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
res.insert(0, s.charAt(i));
}
return res.toString();
}
private String reverse1(String s) {
char[] chars = s.toCharArray();
int i = 0, j = chars.length - 1;
while (i < j) {
char temp = chars[i];
chars[i++] = chars[j];
chars[j--] = temp;
}
return String.valueOf(chars);
}
}
复杂度分析：
- 时间复杂度：O(n)。其中 n 是字符串的长度。
- 空间复杂度：O(n)。使用了大小为 n 的 StringBuilder 空间。
方法3：反向追加
算法思路：
遍历输入字符串每个字符，遇到不为空格的字符时，利用变量 j = i，反向追加到StringBuilder中。
参考代码3:
class Solution {
public String reverseWords(String s) {
StringBuilder res = new StringBuilder();
for(int i= 0; i < s.length();i++){
if(s.charAt(i) != ' ' && (i+1 == s.length() || s.charAt(i+1) == ' ')){
int j = i;
while(j >= 0 && s.charAt(j) != ' '){
res.append(s.charAt(j--));
}
}else if(s.charAt(i) == ' '){
res.append(s.charAt(i));
}
}
return res.toString();
}
}
复杂度分析：
- 时间复杂度：O(n)。其中 n 是字符串的长度,。
- 空间复杂度：O(n)。使用了大小为 n 的 StringBuilder 空间。
方法4：O(1) 交换
算法思路：
遍历字符串每个字符，遇到空格则进行交换，注意在最后一个单词时没有空格，需单独判断。
参考代码4：
class Solution {
public String reverseWords(String s) {
int j=0;
char[] cc = s.toCharArray();
for(int i=0; i<cc.length; i++) {
if(i == cc.length - 1) {
swap(j, i, cc);
}
if(cc[i] == ' ') {
swap(j, i-1, cc);
j = i+1;
}
}
return String.valueOf(cc);
}
private void swap(int j, int curr, char[] cc) {
while(j <= curr) {
char temp = cc[j];
cc[j] = cc[curr];
cc[curr] = temp;
j++;
curr--;
}
}
}
复杂度分析：
- 时间复杂度：O(n)。其中 n 是字符串的长度,。
- 空间复杂度：O(1)。没有使用额外的空间。
以上谢谢大家，求赞求赞求赞！
