151. Reverse Words in a String

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Two Pointers、String

一、題目

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: " hello world "
  • Output: “world hello”
  • Explanation: Your reversed string should not contain leading or trailing spaces.

Example 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.

Constraints:

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

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

二、分析

  • 此題如果搭配 string 常用的函式(在 hackerrank 有提供)，可以很簡單的解題：
    • split function
    vector<string> split(string& s, char del) {
    stringstream ss(s);
    vector<string> res;
    string item;
    while (getline(ss, item, del)) {
        if (!item.empty()) res.push_back(item) // 注意，空白不加到陣列中
    }
    return res;
}
  • 若要做到 O(1) 的 space complexity 的話，只能用 two pointer 了。

三、解題

1. split function

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
string reverseWords(string s) {
    vector<string> svec = split(s, ' ');    // 以空白字元作為分隔
    string res;
    for (int i = svec.size()-1; i >= 0; i--) {
        res = res + " " + svec[i];      // 將陣列反過來組合成字串
    }
    res = res.substr(1);        // 移除多出來的空白字元
    return res;
}
vector<string> split(string& s, char del) {
    stringstream ss(s);
    vector<string> res;
    string item;
    while (getline(ss, item, del)) {
        if (!item.empty()) res.push_back(item); // 注意，空白不加到陣列中
    }
    return res;
}

回目錄 Catalog