LeetCode151.翻转字符串里的单词

1.题目描述

• 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

  单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

  请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

  说明：

  输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
  翻转后单词间应当仅用一个空格分隔。
  翻转后的字符串中不应包含额外的空格。

示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
  
示例 2：
输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

示例 3：
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

示例 4：
输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"
  
示例 5：
输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"
 
提示：
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
进阶：
请尝试使用 O(1) 额外空间复杂度的原地解法。

2.解题思路:

• 2.1.暴力解法
  • 对原始字符串进行split切割，按照空字符切
  • 过滤空字符串
  • 使用stringbuild保存新字符串的内容

    public String reverseWords_v1(String s) {
        if (s == null || "".equals(s = s.trim())) {
            return "";
        }
        String[] splits = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = splits.length - 1; i >= 0; i--) {
            String str = splits[i].trim();
            if (str.length() != 0) {
                sb.append(" ").append(str);
            }
        }
        return sb.substring(1);
    }

• 2.2.双端队列解法
  • 遍历字符串中的字符，遍历到字符时将该字符保存到stringbuild中，
  • 如果便利到空字符了，说明前面的单词遍历结速了，将前面的单词保存到数据结构中（队列或栈）
  • 最后从保存所有单词的数据结构遍历出单词，并用空格进行拼接

    public String reverseWords(String s) {
        if (s == null || "".equals((s = s.trim()))) {
            return "";
        }
        StringBuilder word = new StringBuilder();
        ArrayDeque<String> queue = new ArrayDeque<>();

        System.out.println(s);
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            if (ch != ' ') {
                word.append(ch);
            } else {
                if (word.length() > 0) {
                    queue.offerFirst(word.toString());
                    word.setLength(0);
                }
            }
        }
        if (word.length() > 0) {
            queue.offerFirst(word.toString());
        }
        return String.join(" ", queue);
    }

3.总结

• 解法总结
  • 要将字符串中的单词进行翻转后返回，而且要过滤掉多余的空格
  • 在遍历原始字符串时，遍历到字符保存起来，当遍历到空格时，说明前面遍历结束一个单词，将该单词进行保存
  • 最后将所有的单词反向输出，并用空格拼接。如果不想反向输出，则在添加时最后的单词添加到队列的头部
• 双端队列