[LeetCode] 151. Reverse Words in a String

Posted on | In

Problem

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

Example 1:

1
2
Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

1
2
3
Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

1
2
3
Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

Explanation 1

  1. If we do this problem without programming, first we would split each word no matter how many spaces in between each word. We can use replaceAll to replace more than one space into one space, then split by space.

  2. Now, we have an array of many words, and we want to put the last whole word at the beginning, second last whole word in the second position, etc. We can simply loop from the end to beginning, and put each element (word) into the stringbuilder. At the end, we can just return this stringbuilder as string.

Solution 1.1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String reverseWords(String s) {
        String trimStr = s.trim();
        String[] strArr = trimStr.split("\s+");
        StringBuilder sb = new StringBuilder();

        for (int i = strArr.length - 1; i >= 1; i--) {
            sb.append(strArr[i] + " ");
        }
        sb.append(strArr[0]);

        return sb.toString();
    }
}

Solution 1.2

1
2
3
4
5
6
7
class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split(" +");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
}

Explanation 2

  1. We can create two pointers start and end point to a word’s beginning index and end index (exclusive), and define n is the length of the string.

  2. While start < n && s[start] == ' ', then we keep increase start. Now, start is pointing to the beginning of the word. Then update end = start + 1, while end < n && s[end] != ' ', then we keep increase end. Now, end is pointing to the ending of the word (exlusive).

  3. If res is empty, we simply update res to s[start, end]. Else, we append s[start, end] + " " to the beginning of the res. After updating res, we then update start = end + 1. Repeat step 2 and step 3 while start < n. If start is equal to n, we need to stop and return the result.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String reverseWords(String s) {
        int start = 0, end = 0;
        int n = s.length();
        String res = "";

        while (start < n) {
            while (start < n && s.charAt(start) == ' ') start += 1;
            if (start == n) break;
            end = start + 1;
            while (end < n && s.charAt(end) != ' ') end += 1;
            if (res.length() == 0) res = s.substring(start, end);
            else res = s.substring(start, end) + " " + res;
            start = end + 1;
        }

        return res;
    }
}