剑指Offer-面试题58-I-翻转单词顺序

2020-05-06

题目描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

示例1：

1 2	输入: "the sky is blue" 输出: "blue is sky the"

示例2：

1
2
3

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例3：

1
2
3

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路

设置双指针i和j，从后往前遍历。

使用trim()将字符串首尾空格去掉
遍历字符串，i代表单词的左边界，j为单词右边界

代码

class Solution{
    public String reverseWords(String s){
        s = s.trim();   //去掉字符串首尾的空格
        int i = s.length() - 1;
        int j = i;
        StringBuilder result = new StringBuilder();
        //遍历字符串
        while(i >= 0){
            //找单词，当i!=' '的时候就左移，遇到空格则停下
            while(i>=0 && s.charAt(i)!=' '){
                i--;
            }
            //找到了单词，区间为[i+1,j]，substring为左开右闭，将单词拼接到result后并加上空格
            result.append(s.substring(i+1,j+1) + " ");
            //找下一个单词的右边界，当i=' '时就左移（跳过空格），遇到不是空格的字符就停下，更新j
            while(i>=0 && s.charAt(i)==' '){
                i--;
            }
            j = i;
        }
        //返回去掉首尾空格的字符串
        return result.toString().trim();
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。