[LeetCode] 186. Reverse Words in a String II

Posted on | In

Problem

Given an input string , reverse the string word by word.

Example:

1
2
Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Note:

  • A word is defined as a sequence of non-space characters.
  • The input string does not contain leading or trailing spaces.
  • The words are always separated by a single space.

Follow up: Could you do it in-place without allocating extra space?

Explanation

  1. Similar to 151. Reverse Words in a String, we can first reverse each word, at the end, we reverse the whole string.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    void reverse(char[] s, int left, int right) {
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left += 1;
            right -= 1;
        }
    }

    public void reverseWords(char[] s) {
        for (int i = 0, left = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                reverse(s, left, i-1);
                left = i + 1;
            }
        }
        reverse(s, 0, s.length-1);
    }
}