151. Reverse Words in a String

Problem

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.

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?

Solution

Problem

• 주어진 문자열 s에서 단어의 순서를 거꾸로 변경해야 함.
• 단어는 공백이 아닌 연속된 문자들로 정의됨.
• 여러 개의 공백을 단 하나의 공백으로 축소해야 함.
• 문자열 양쪽 끝의 공백은 제거해야 함.

Constraints

1. 1 ≤ s.length ≤ 10⁴

• 문자열의 길이가 최대 10,000이므로 O(N²) 이상의 알고리즘은 비효율적일 수 있음.
• 따라서, O(N) 또는 O(N log N) 정도의 알고리즘을 찾아야 함.

2. s는 영어 대소문자, 숫자, 공백 문자(' ')로만 구성됨.

• 특수문자에 대한 예외 처리는 필요 없음.

3. 적어도 하나의 단어가 존재함.

• 빈 문자열("")이 들어올 가능성은 없음.

4. 출력 문자열에서는 단어 사이에 공백 하나만 남겨야 함.

• 예를 들어 "a good example" → "example good a"

5. Follow-up: O(1) 추가 공간으로 해결할 수 있는가?

• 문자열이 mutable(변경 가능)하다면 in-place로 해결할 수 있는 방법을 고려해야 함.

Methodology

1. 기본적인 방법 (O(N) 공간, O(N) 시간)

• 문자열을 단어 단위로 분리 (split())
• 단어 순서를 뒤집기 (reverse())
• 공백을 하나의 공백으로 합쳐서 반환 (join())
• 이 방식은 직관적이지만, 추가적인 배열 공간 O(N)이 필요함.

2. O(1) 추가 공간으로 해결하는 방법 (Follow-up)

• 문자열 전체를 뒤집음.
• 각 단어를 다시 개별적으로 뒤집음.
• 여러 개의 공백을 하나로 정리함.
• in-place로 진행하여 O(1) 추가 공간 유지.

Code

시간/공간 복잡도 분석

• 시간 복잡도:
  문자열을 한번 순회하며 단어를 분리 → O(N)
  단어 리스트를 뒤집기 → O(N)
  단어를 다시 결합하기 → O(N)
  따라서 전체 시간 복잡도는 O(N).

• 공간 복잡도:
  첫 번째 방법에서는 단어 리스트를 저장하므로 O(N) 추가 공간이 필요.
  두 번째 방법(in-place)은 O(1) 추가 공간을 유지.

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

string reverseWords(string s) {
    stringstream ss(s);
    string word;
    vector<string> words;

    // 공백을 기준으로 단어 분리
    while (ss >> word) {
        words.push_back(word);
    }

    // 단어 순서 뒤집기
    reverse(words.begin(), words.end());

    // 단어들을 다시 공백으로 결합
    string result;
    for (int i = 0; i < words.size(); i++) {
        if (i > 0) result += " ";
        result += words[i];
    }

    return result;
}

//
int main() {
    string s = "  hello   world  ";
    cout << "Output: \"" << reverseWords(s) << "\"" << endl;  // Expected: "world hello"
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

// in-place
void reverseString(string &s, int left, int right) {
    while (left < right) {
        swap(s[left++], s[right--]);
    }
}

string reverseWordsInPlace(string s) {
    int n = s.size();
    
    // 1. 전체 문자열을 뒤집기
    reverseString(s, 0, n - 1);
    
    // 2. 각 단어를 개별적으로 뒤집기
    int start = 0, end = 0, writeIndex = 0;
    while (end < n) {
        // 공백 건너뛰기
        while (end < n && s[end] == ' ') end++;
        if (end == n) break;

        // 단어의 시작점
        start = end;

        // 단어의 끝까지 이동
        while (end < n && s[end] != ' ') end++;

        // 단어를 뒤집기
        reverseString(s, start, end - 1);

        // 단어를 앞으로 당겨서 정리
        if (writeIndex != 0) s[writeIndex++] = ' ';
        while (start < end) s[writeIndex++] = s[start++];
    }

    // 3. 문자열의 크기를 조정하여 불필요한 공백 제거
    s.resize(writeIndex);

    return s;
}

// 
int main() {
    string s = "  hello   world  ";
    cout << "Output: \"" << reverseWordsInPlace(s) << "\"" << endl;  // Expected: "world hello"
    return 0;
}