package com.leetcode.leetcode.licm;
import org.apache.logging.log4j.util.Strings;
/**
* @description: /**
* * 151. 翻转字符串里的单词
* * 给你一个字符串 s ,逐个翻转字符串中的所有 单词 。
* * <p>
* * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
* * <p>
* * 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
* * <p>
* * 说明:
* * <p>
* * 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
* * 翻转后单词间应当仅用一个空格分隔。
* * 翻转后的字符串中不应包含额外的空格。
* * <p>
* * <p>
* * 示例 1:
* * <p>
* * 输入:s = "the sky is blue"
* * 输出:"blue is sky the"
* * 示例 2:
* * <p>
* * 输入:s = " hello world "
* * 输出:"world hello"
* * 解释:输入字符串可以在前面或者后面包含多余的空格,但是翻转后的字符不能包括。
* * 示例 3:
* * <p>
* * 输入:s = "a good example"
* * 输出:"example good a"
* * 解释:如果两个单词间有多余的空格,将翻转后单词间的空格减少到只含一个。
* * 示例 4:
* * <p>
* * 输入:s = " Bob Loves Alice "
* * 输出:"Alice Loves Bob"
* * 示例 5:
* * <p>
* * 输入:s = "Alice does not even like bob"
* * 输出:"bob like even not does Alice"
* * <p>
* * <p>
* * 提示:
* * <p>
* * 1 <= s.length <= 104
* * s 包含英文大小写字母、数字和空格 ' '
* * s 中 至少存在一个 单词
* * <p>
* * <p>
* * 进阶:
* * <p>
* * 请尝试使用 O(1) 额外空间复杂度的原地解法。
* *
* * @param s
* * @return
* @author:licm
* @create:2021-07-13 09:22
**/
public class Lc_151翻转字符串里的单词 {
/**
* 双指针思路,不适用额外的空间
* <p>
* 第一步 去除首尾空格
* 第二步 反转所有字符串
* 第三步 反转没一个字符串
*
* @param s
* @return
*/
public static String reverseWords(String s) {
StringBuilder sb = removeSpace(s);
reverseString(sb, 0, sb.length() - 1);
reverseEachWord(sb);
return sb.toString();
}
/**
* 第一步 利用双指针去除首尾空格
*/
private static StringBuilder removeSpace(String s) {
StringBuilder sb = new StringBuilder();
int left = 0;
int right = s.length() - 1;
while (s.charAt(left) == ' ') {
left++;
}
while (s.charAt(right) == ' ') {
right--;
}
while (left <= right) {
if (s.charAt(left) != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(s.charAt(left));
}
left++;
}
return sb;
}
private static void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
private static void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
public static void main(String[] args) {
String s = " the sky is blue ";
System.out.println(reverseWords(s));
}
}
不会,我可以学;落后,我可以追赶;跌倒,我可以站起来!
版权声明:本文内容来自第三方投稿或授权转载,原文地址:https://blog.51cto.com/u_12550160/3181013,作者:小傻孩丶,版权归原作者所有。本网站转在其作品的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如因作品内容、版权等问题需要同本网站联系,请发邮件至ctyunbbs@chinatelecom.cn沟通。