一，反转字符串
344. 反转字符串 - 力扣（LeetCode）
https://leetcode.cn/problems/reverse-string/
1，双指针
class Solution { public: void reverseString(vector<char>& s) { int n = s.size(); for (int left = 0, right = n - 1; left < right; ++left, --right) { swap(s[left], s[right]); } } };
复杂度分析
时间复杂度：O(N)，其中 NN 为字符数组的长度。一共执行了 N/2 次的交换。
空间复杂度：O(1)。只使用了常数空间来存放若干变量。
二，反转字符串中的单词|||
557. 反转字符串中的单词 III - 力扣（LeetCode）
https://leetcode.cn/problems/reverse-words-in-a-string-iii/
1，使用额外空间
思路与算法
开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
class Solution { public: string reverseWords(string s) { string ret; int length = s.length(); int i = 0; while (i < length) { int start = i; while (i < length && s[i] != ' ') { i++; } for (int p = start; p < i; p++) { ret.push_back(s[start + i - 1 - p]); } while (i < length && s[i] == ' ') { i++; ret.push_back(' '); } } return ret; } };
复杂度分析
时间复杂度：O(N)，其中 NN 为字符串的长度。原字符串中的每个字符都会在 O(1) 的时间内放入新字符串中。
空间复杂度：O(N)。我们开辟了与原字符串等大的空间。
2，原地解法
思路与算法
此题也可以直接在原字符串上进行操作，避免额外的空间开销。当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符……如此反复，就可以在原空间上翻转单词。
需要注意的是，原地解法在某些语言（比如 Java，JavaScript）中不适用，因为在这些语言中 String 类型是一个不可变的类型。
class Solution { public: string reverseWords(string s) { int length = s.length(); int i = 0; while (i < length) { int start = i; while (i < length && s[i] != ' ') { i++; } int left = start, right = i - 1; while (left < right) { swap(s[left], s[right]); left++; right--; } while (i < length && s[i] == ' ') { i++; } } return s; } };
还可以直接定义left，right两个指针。
复杂度分析
时间复杂度：O(N)。字符串中的每个字符要么在O(1) 的时间内被交换到相应的位置，要么因为是空格而保持不动。
空间复杂度：O(1)。因为不需要开辟额外的数组。
