【模拟, 双指针】反转字符串中的单词

题目

151. 反转字符串中的单词

---

给你一个字符串 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"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 10^4
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

**进阶：**如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

解题

方法一：API

思路

直接上 API，对字符串去除前后空格，根据空字符分割，翻转，最后拼接。

代码

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

方法二：模拟 双指针

思路

先把整个字符串翻转，然后再把每个单词翻转，翻转后去除多余空格，具体操作见代码注释。

代码

class Solution {
    char[] chs;

    public String reverseWords(String s) {
        int n = s.length();
        // 准备一个长度为 n+1 的字符数组
        chs = new char[n + 1];
        chs[0] = ' '; // 把第一个字符置为空格
        // 把字符串放进剩下的区域
        System.arraycopy(s.toCharArray(), 0, chs, 1, n);
        // 这样做的目的是: 在字符数组翻转后 空格就去到了末尾
        // 这样在给定字符串没有前导零时 循环处理单词的时候最后一个单词不用额外处理
        ++n;
        // 翻转字符串
        reverse(0, n - 1);
        int begin = 0, end = n - 1;
        // 找到第一个单词开始位置
        while (chs[begin] == ' ') ++begin;
        int oughtToEnd = n; // 每个单词应该结束的位置（只隔一个空格）
        // wordBegin: 每个单词现在的开始索引; oughtToBegin: 每个单词应该开始的位置
        for (int i = begin + 1, wordBegin = begin, oughtToBegin = 0; i < n; ++i) {
            // 遇到空格 单词结束
            if (chs[i] == ' ') {
                // 该单词现在的结尾索引
                int wordEnd = i - 1;
                // 翻转该单词
                reverse(wordBegin, wordEnd);
                // 根据oughtToBegin以及单词长度算出oughtToEnd
                oughtToEnd = oughtToBegin + wordEnd - wordBegin;
                // 把单词向前移动（去除多余空格）
                for (int offset = 0; offset <= wordEnd - wordBegin; ++offset) {
                    chs[oughtToBegin + offset] = chs[wordBegin + offset];
                }
                // 把单词原来的位置置为空格
                for (int j = oughtToEnd + 1; j <= wordEnd; ++j) chs[j] = ' ';
                oughtToBegin = oughtToEnd + 2;
                // 找到下一个单词的开头
                while (i < n && chs[i] == ' ') ++i;
                wordBegin = i;
            }
        }
        // 返回截断后面空格后的字符串
        return String.valueOf(chs).substring(0, oughtToEnd + 1);
    }

    void reverse(int left, int right) {
        for (; left < right; ++left, --right) {
            char tmp = chs[left];
            chs[left] = chs[right];
            chs[right] = tmp;
        }
    }
}