[LeetCode] 151 Reverse Words in a String

Description

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "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.

Example 4:

Input: s = " Bob Loves Alice "
Output: "Alice Loves Bob"

Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

• 1 <= s.length <= 10^4
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

---

풀이

적어도 단어 한 개는 있다고 했으니까 s의 길이가 1일 때는 이 1개의 문자가 공백이 아닌 단어라는 뜻이므로 s 그대로 반환하도록 했다.

while을 사용하여 s의 문자를 뒤에서부터 앞까지 하나씩 본다.

현재 문자(end)가 공백이면 end를 1개 줄인다.

공백이 아닌 문자라면 start 지점을 찾는다.
start는 end-1로 지정을 한다.
그래서 start가 0과 크거나 같으면서 공백이 아닐 때까지 start를 하나씩 줄이면서 while을 돌린다.

while을 빠져나오면 단어를 찾았다는 뜻이므로 처음 단어를 넣을 때만 공백문자를 추가하지 않고 바로 해당 단어만 추가하고, 이미 넣은 단어가 존재할 때는 공백문자를 넣은 뒤 해당 단어를 넣는다.

마지막에는 stringbuilder를 string으로 바꿔서 반환한다.

---

코드

class Solution {
    public String reverseWords(String s) {
        //base case
        if (s.length() == 1) return s;

        StringBuilder sb = new StringBuilder();
        int end = s.length() - 1;
        
        while (end >= 0) {
            if (s.charAt(end) != ' ') {
                int start = end - 1;
                while (start >= 0 && s.charAt(start) != ' ') {
                    start--;
                }
                if (sb.length() != 0) sb.append(" ");
                sb.append(s, start + 1, end + 1);
                end = start;
            } else {
                end--;
            }
        }
        return sb.toString();
    }
}