[LeetCode] 151. Reverse Words in a String

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