leetcode：557. 反转字符串中的单词 III

题目

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

  1. 输入：s = "Let's take LeetCode contest"
  2. 输出："s'teL ekat edoCteeL tsetnoc"
  1. 输入： s = "God Ding"
  2. 输出："doG gniD"

解答 & 代码

原地修改：遍历字符串 s，找到每个单词的起始位置 start 和结束位置 end，翻转 s[start, end) 部分

  1. class Solution {
  2. public:
  3.     string reverseWords(string s) {
  4.         int idx = 0;
  5.         while(idx < s.size())
  6.         {
  7.             int start = idx;
  8.             while(idx < s.size() && s[idx] != ' ')
  9.                 ++idx;
  10.             int end = idx;
  11.             reverse(s.begin() + start, s.begin() + end);
  12.             ++idx;
  13.         }
  14.         return s;
  15.     }
  16. };

复杂度分析：设字符串长为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(1)：原地修改

执行结果：

  1. 执行结果：通过
  3. 执行用时：12 ms, 在所有 C++ 提交中击败了 58.32% 的用户
  4. 内存消耗：9.4 MB, 在所有 C++ 提交中击败了 66.78% 的用户