557. 反转字符串中的单词 III-字符串,双指针(易)

题目描述

题目链接:https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/submissions/

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1:

输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

解题思路

思路就是我们每找到一个空格, 就对空格前的字符串进行反转.
这里涉及到一个JAVA SE的基础知识: JAVA的String不可以被修改, 但是StringBuilder可以, 或者用toCharArray转成char[]数组.
这里直接采用String.toCharArray(), 把字符串转成字符数组, 就可以间接进行修改, 最后返回一个新的字符串即可.

复杂度分析

T: O(n)
S: O(n), 如果是C++解题, 可以直接在原字符串上修改, O(1)

代码

class Solution {
    //反转ii到jj区间的字符串
    public void reverse(char[] c, int ii, int jj) {
        for (int i = ii, j = jj; i < j; i++,j--) {
            char t = c[i];
            c[i] = c[j];
            c[j] = t;
        }
    }
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return s;
        char[] c = s.toCharArray();
        int i = 0, j = 0;
        while (i < s.length()) {
            while (j < s.length() && c[j] != ' ') j++;
            reverse(c, i, j-1);
            i = j+1;
            j++;
        }
        return new String(c);
    }
}