# LeetCode 151. 颠倒字符串中的单词

LeetCode 151. Reverse Words in a String

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。 s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个

提示：

• $1 \le$ s.length $\le 10^4$
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶： 如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 $O(1)$ 额外空间复杂度的 原地 解法。

# Method 1: 双指针

# 算法思路

1. 移除字符串中多余的空格，包括字符串首部和尾部的空格以及单词之间的多个空格

2. 翻转整个字符串

3. 逐个翻转每个单词

以 "a good example" 为例：

• 移除多余空格："a good example"
• 翻转字符串："elpmaxe doog a"
• 翻转单词："example good a"

可参考

• LeetCode 27. 移除元素
• LeetCode 344. 反转字符串
• LeetCode 557. 反转字符串中的单词 III

# 算法流程

1. 去除多余空格

   • 定义快慢指针 fast 和 slow ， slow 指向 0 ， fast 指向从左往右的第一个非空格字符
   • 将 s[fast] 赋给 s[slow] ，然后移动 fast 和 slow 指针，重复该过程，特别地，如果 fast 遇到连续的多个空格，只需将一个空格赋给 s[left]
   • 当 fast 移动到字符串的尾后时， slow 指向的是原字符串的最后一个字符。如果 s[slow] 是空字符，将 slow 指针向左移动，直到 slow 指向非空字符

2. 调整字符串 s 的长度：上一步中的 slow 指向最后一个有效字符，故，有效字符串的长度为 slow + 1

3. 翻转整个字符串

   • 定义 reverse 函数，实现左右指针 left 和 right 之间所有字符的翻转：交换 s[left] 与 s[right] ，并将 left 向右移动、将 right 向左移动

4. 翻转字符串中的每个单词

   • 定义 start 和 end 指针， start 指向单词的起始位置，当 end 指向单词后的空格时或者指向字符串的尾后时，调用 reverse 函数翻转 start 到 end - 1 之间的字符

# 代码实现

// 将 left 到 right 之间的所有字符反转

void reverse(string &s, int left, int right) {

    while (left < right)

        swap(s[left++], s[right--]);

}

// 双指针，去掉多余空格

void removeExtraSpaces(string &s) { // 双指针法

    int slow = 0, fast = 0;

    while (fast < s.size() && s[fast] == ' ') fast++; // 跳过字符串首部的空格

    for (; fast < s.size(); fast++) {

        if (s[fast] == ' ' && s[fast - 1] == ' ')     // 跳过重复的空格

            continue;

        s[slow++] = s[fast];       // 移动元素

    }

    slow--;                        //slow 指向元素移动后的末尾字符

    while (s[slow] == ' ') slow--; //slow 移到最后一个非空格字符的位置（排除字符串尾部的空格）

    s.resize(slow + 1);            // 调整 s 的大小

}

// 翻转字符串中的单词

string reverseWords(string s) {

    removeExtraSpaces(s);        // 移除多余空格

    reverse(s, 0, s.size() - 1); // 反转整个字符串

    int start = 0, end = 0;

    while (end <= s.size()) {    // 双指针法，反转每个单词

        if (s[end] == ' ' || end == s.size()) { //end 遇到空格或者到达尾后，反转单词

            reverse(s, start, end - 1);

            start = end + 1;     // 下一个单词的起点

        }

        end++;

    }

    return s;

}

# 复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

有关 多余空格的去除 ，还可以参考 代码随想录：翻转字符串里的单词 中的思路

# Method 2: 一次遍历

代码实现：

string reverseWords(string s) {

    reverse(s.begin(), s.end()); // 反转整个字符串（库函数）

    int index = 0;

    for (int start = 0; start < s.size(); ++start) { //start 用于寻找每个单词的第一个字母

        if (s[start] != ' ') { // 遇到单词的第一个字母

            if (index != 0) s[index++] = ' ';  // 添加空格，然后将 index 移动到下一个单词的开头位置

            int end = start;   // 单词的最后一个字母

            while (end < s.size() && s[end] != ' ') s[index++] = s[end++]; // 寻找单词的最后一个字母

            reverse(s.begin() + index - (end - start), s.begin() + index); // 反转整个单词

            start = end;

        }

    }

    s.resize(index); // 修改字符串 s 的长度（提取有效字符）

    return s;

}

参考：leetcode-solution

# LeetCode 208. 实现 Trie (前缀树)

208. Implement Trie (Prefix Tree)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true （即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

输出：
[null, null, true, false, true, null, true]

解释：
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• $1 \le$ word.length , prefix.length $\le 2000$
• word 和 prefix 仅由小写英文字母组成
• insert 、 search 和 startsWith 调用次数 总计 不超过 $3 \times 10^4$ 次

# 思路

Trie 又称前缀树或字典树，是一种用于快速查询 某个字符串 / 字符前缀 是否存在的数据结构

Trie 的每个节点包含以下字段：

• 指向子节点的指针数组 children
• 布尔字段 isEnd，表示该节点是否为字符串的结尾

例如：

# Method: 字典树

算法思路：

本题的 children 数组的长度为 26，即小写英文字母的数量，其中，children [0] 对应 a，children [25] 对应 z

定义函数 Trie* searchPrefix (string prefix) 用于判断字典树是否存在前缀 prefix ：若搜索到了前缀的末尾，就说明字典树中存在该前缀，否则，字典树不存在该前缀

特别地，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串

代码实现：

class Trie {

private:

    Trie* children[26];

    bool isEnd;

    Trie* searchPrefix(string prefix) { // 判断字典树是否存在前缀 prefix

        Trie* node = this;

        for (auto c : prefix) {

            int tmp = c - 'a';

            if (node->children[tmp] == nullptr) // 不存在 prefix，返回空指针

                return nullptr;

            node = node->children[tmp];

        }

        return node; // 存在 prefix，则返回末尾指针

    }

public:

    Trie() {

        isEnd = false;

        for(int i = 0; i < 26; ++i)

            children[i] = nullptr;

    }

    ~Trie() { // 析构函数，避免内存泄漏

        for (int i = 0; i < 26; ++i) {

            if (children[i] != nullptr)

                delete children[i];

        }

    }

    void insert(string word) { // 插入字符串 word

        Trie* node = this;

        for (auto c : word) {

            int tmp = c - 'a';

            if (node->children[tmp] == nullptr)

                node->children[tmp] = new Trie();

            node = node->children[tmp];

        }

        node->isEnd = true;

    }

    bool search(string word) { // 判断字符串 word 是否存在

        Trie* node = this->searchPrefix(word);

        return node != nullptr && node->isEnd;

    }

    bool startsWith(string prefix) { // 判断前缀 prefix 是否存在

        return this->searchPrefix(prefix) != nullptr;

    }

};

/**

 * Your Trie object will be instantiated and called as such:

 * Trie* obj = new Trie();

 * obj->insert(word);

 * bool param_2 = obj->search(word);

 * bool param_3 = obj->startsWith(prefix);

 */

时间复杂度：初始化所需时间为 $O(1)$，其余操作所需时间为 $O(\vert S \vert)$，其中，$\vert S \vert$ 是每次插入或查询的字符串的长度

空间复杂度：$O(\vert T \vert \cdot \vert \Sigma \vert)$，其中，$\vert T \vert$ 是插入字典树中的所有字符串的长度之和，$\vert \Sigma \vert$ 是字符集的大小（本题 $\vert \Sigma \vert = 26$）

参考：

• leetcode-solution
• 宫水三叶

# LeetCode 28. 实现 strStr ()

LeetCode 28. Implement strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

Clarification:

• 当 needle 是一个空字符串时，我们应该返回什么？

• 当 needle 是空字符串时，我们将返回 0。这与 C 语言的 strstr() 和 Java 的 indexOf() 一致。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

提示：

• $1 \le$ haystack.length , needle.length $\le 10^4$
• haystack and needle consist of only lowercase English characters.

# 思路

本题是经典的字符串单模匹配的模型，可以使用字符串匹配算法解决，常见的字符串匹配算法包括暴力匹配、Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunday 算法等

力扣官方题解：实现 strStr ()

# Method 1: 暴力搜索

基本思路：让字符串 needle 与字符串 haystack 中所有长度为 m 的子串均匹配一次，其中， m 为字符串 needle 的长度

// 检查字符串 haystack 中以索引 start 开头的一连串字符是否与 needle 字符串匹配

bool isSubStr(string haystack, int start, string needle) {

    for (auto c : needle) {

        if (haystack[start] != c)

            return false;

        start++;

    }

    return true;

}

int strStr(string haystack, string needle) {

    for (int i = 0; i < haystack.size(); i++) {

        if (isSubStr(haystack, i, needle))

            return i; 

    }

    return -1;

}

时间复杂度：$O(n \times m)$，其中，$n$ 为字符串 haystack 的长度，$m$ 为字符串 needle 的长度

空间复杂度：$O(1)$

# Method 2: KMP 算法

文本串为 haystack ，模式串为 needle ，利用 KMP 算法进行字符串匹配

算法流程：

1. 构造 next 数组，用于查找回退位置

2. 利用 next 数组进行匹配，定义 i 为文本串索引， j 为模式串索引，执行循环：

   • 若模式串字符 needle[j] 与文本串字符 haystack[i] 相同，则将 i 和 j 同时右移
   • 若不相同，连续执行 j = next[j - 1] ，直到 needle[j] == haystack[i] 或 j == 0

具体原理及步骤可参阅 KMP 算法

代码实现：

// 计算 next 数组

void getNext(vector<int> &next, string s) {

    int prefix = 0;

    next[0] = 0;

    for (int suffix = 1; suffix < s.size(); suffix++) {

        while (prefix > 0 && s[prefix] != s[suffix])

            prefix = next[prefix - 1];

        if (s[prefix] == s[suffix])

            prefix++;

        next[suffix] = prefix;

    }

}

// 字符串匹配

int strStr(string haystack, string needle) {

    vector<int> next(needle.size(), 0);

    getNext(next, needle);

    int j = 0;

    for (int i = 0; i < haystack.size(); i++) {

        while (j > 0 && needle[j] != haystack[i]) //needle [j] 与 haystack [i] 不同，回退 j

            j = next[j - 1];

        if (needle[j] == haystack[i])       //needle [j] 与 haystack [i] 相同，右移 i 和 j

            j++;

        if (j == needle.size())             // 匹配完成

            return (i - needle.size() + 1); // 正确匹配的起点索引为 i - needle.size () + 1

    }

    return -1;

}

时间复杂度：$O(n + m)$

空间复杂度：$O(m)$，使用额外空间存储 next 数组

参考：

• 代码随想录
• 力扣官方题解

# LeetCode 344. 反转字符串

LeetCode 344. Reverse String

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 $O(1)$ 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

• $1 \le$ s.length $\le 10^5$
• s[i] 都是 ASCII 码表中的可打印字符

# Method: 双指针

解题步骤：

1. 定义 left 指向字符数组首元素， right 指向字符数组尾元素
2. 当 left < right 时，执行循环：交换 s[left] 和 s[right] ， left 指针右移一位； right 指针左移一位

代码如下：

void reverseString(vector<char>& s) {

    int left = 0, right = s.size() - 1; // 双指针

    while (left < right)

        swap(s[left++], s[right--]);    // 交换，并移动指针

}

时间复杂度：$O(N)$，其中 $N$ 为字符数组的长度，一共执行了 $N/2$ 次的交换

空间复杂度：$O(1)$

如果库函数仅仅是解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数，例如这里使用的 swap 函数

swap 函数具有两种实现方式，以交换 s[left] 和 s[right] 为例：

1. 直接交换数值

    int temp = s[left]; // 中间量
    s[left] = s[right];
    s[right] = temp;
   

2. 位运算（异或）

    s[left] ^= s[right]; // 中间量
    s[right] ^= s[left]; // 将中间量与 s[right] 进行异或运算， = 号右边得到的是原始的 s[left]
    s[left] ^= s[right]; // 将中间量与 s[right] （即原始的 s[left] ） 进行异或运算， = 号右边得到的是原始的 s[right]
   

# LeetCode 459. 重复的子字符串

LeetCode 459. Repeated Substring Pattern

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1：

输入：s = "abab"
输出：true
解释：可由子串 "ab" 重复两次构成

示例 2：

输入：s = "aba"
输出：false

示例 3：

输入：s = "abcabcabcabc"
输出：true
解释：可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• $1 \le$ s.length $\le 10^4$
• s 由小写英文字母组成

# 思路

检查字符串是否由重复的子串组成，即，验证字符串 s 的周期性

可以通过构造 next 数组，获取字符串 s 的周期信息

next 数组最后一位元素记录了整个字符串的 最长相同前后缀 的长度，记作 next[s.size() - 1] 。若字符串具有周期性， next[s.size() - 1] 就应该是周期的整数倍，且应该是 字符串的总周期数 - 1 倍。换而言之， s.size() - next[s.size() - 1] 就是周期的长度

有关 next 数组及其构造，可参阅 KMP 算法

以字符串 "abcabcabc" 为例，其 next 数组为：

其周期长度 = 字符串总长度 - next 数组最后一位元素值 = 9 - 6 = 3

因此，可以作出以下结论：若 next[s.size() - 1] 非零 且 字符串总长度 s.size() 能够被 s.size() - next[s.size() - 1] 整除 ，则，字符串具有周期性，即，可以由子串重复多次而构成

有关该方法正确性的理论证明，可参考 力扣官方题解：重复的子字符串（方法三）

# Method：KMP 算法

解题流程：

1. 构造 next 数组
2. 找到 next 数组最后一位元素，即， next[s.size() - 1]
3. 判断 next[s.size() - 1] 是否为 0
   • 若 next[s.size() - 1] == 0 ，字符串不存在周期， return false
   • 若 next[s.size() - 1] != 0 ，判断 s.size() 是否能被 s.size() - next[s.size() - 1] 整除
     • 若能够被整除，字符串具有周期性， return true
     • 若不能被整除， return false

代码实现：

// 构造 next 数组

void getNext(vector<int> &next, string s) { // 注意，要对 next 加引用符 &

    int prefix = 0;

    next[0] = 0;

    for (int suffix = 1; suffix < s.size(); suffix++) {

        while (prefix > 0 && s[prefix] != s[suffix])

            prefix = next[prefix - 1];

        if (s[prefix] == s[suffix])

            prefix++;

        next[suffix] = prefix;

    }

}

bool repeatedSubstringPattern(string s) {

    vector<int> next(s.size(), 0);

    getNext(next, s);

    //for (auto c : next)  // 打印 next 数组

    //     cout << c << " ";

    // cout << endl;

    int temp = next[s.size() - 1];

    if (temp != 0 && s.size() % (s.size() - temp) == 0)

        return true;

    return false;

}

时间复杂度：$O(n)$，其中，$n$ 是字符串 s 的长度

空间复杂度：$O(n)$

可以通过打印 next 数组来检查 next 数组的构造是否正确，并帮助理解做题思路

# LeetCode 541. 反转字符串 II

LeetCode 541. Reverse String II

给定一个字符串 s 和一个整数 k ，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

• $1 \le$ s.length $\le 10^4$
• s 仅由小写英文组成
• $1 \le$ k $\le 10^4$

# 思路

直接按题意进行模拟：

反转每个下标从 2k 的倍数开始的、长度为 k 的子串，若该子串长度不足 k ，则反转整个子串

# Method: 双指针

解题步骤：

将字符串 s 分成若干段长为 2k 的区间（最后一段不足 2k 也同样视为一个区间），针对每个区间执行以下操作

• 若区间内的字符多于 k 个，反转前 k 个字符，反转操作与 LeetCode 344. 反转字符串 一致
• 若区间内的字符少于 k 个，反转所有字符

其中，针对区间的遍历，只需遍历区间的起点，即，以 i = 0 为起点，每次按照 i = i + 2 * k 更新 i ，当 i >= s.size() 时结束遍历

代码实现：

// 反转 left 到 right 之间的字符

void reverse(string &s, int left, int right) {

    while (left < right)

        swap(s[left++], s[right--]);

}

// 反转字符串

string reverseStr(string s, int k) {

    for (int i = 0; i < s.size(); i += 2 * k) { // 每 2k 个字符，进行一次 前 k 个字符的反转

        if (i + k - 1 < s.size()) {  // 剩余字符多于 k 个，反转前 k 个字符

            reverse(s, i, i + k - 1);

            continue;

        }

        reverse(s, i, s.size() - 1); // 剩余字符少于 k 个，将全部剩余字符反转

    }

    return s;

}

特别地，可以将上述 for 循环写成：

for (int i = 0; i < s.size(); i += 2 * k)
    reverse(s, i, min(i + k - 1, num.size() - 1));

时间复杂度：$O(n)$，其中，$n$ 为字符串长度

• 遍历 i 的时间复杂度为 $O(n / k)$
• 每反转 k 个字符的时间复杂度为 $O(k)$

空间复杂度：$O(1)$

当需要以固定规律对字符串逐段处理时，可试着在 for 循环的表达式上做做文章

参考：力扣官方题解：反转字符串 II

# LeetCode 557. 反转字符串中的单词 III

LeetCode 557

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

示例 1：

输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

示例 2：

输入：s = "God Ding"
输出："doG gniD"

提示：

• $1 \le$ s.length $\le 5 \times 10^4$
• s 包含可打印的 ASCII 字符
• s 不包含任何开头或结尾空格
• s 里 至少 有一个词
• s 中的所有单词都用一个空格隔开

# Method 1: 双指针（原地解法）

当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符…… 如此反复，就可以在原空间上翻转单词。

具体流程如下：

1. 指针 left 指向第一个字符或空字符前一个字符（双指针中的左端指针）
2. 指针 search 向右搜索
3. 当 search 搜索到空字符或尾后时，将 search - 1 赋给双指针中的右端指针 right
4. 将 left 和 right 之间的所有字符反转

重复上述操作，直到所有字符均已被反转

string reverseWords(string s) {

    int search = 0;

    auto n = s.size();

    while (search < n)

    {

        int left = search;                       //left 指向第一个字符或空字符后一个字符

        while (s[search] != ' ' && search < n)   // 向右搜索，直到遇到空字符或者最后一个字符

        {

            search++;

        };

        int right = search - 1;                  //right 指向空字符前一个位置，即，单词最后一个字符所在位置

        while (left < right)                     // 反转单词

        {

            swap(s[left], s[right]);

            left++;

            right--;

        };

        search++;                                // 继续搜索

    };

    return s;

}

时间复杂度：$O(N)$ ，字符串中的每个字符要么在 $O(1)$ 的时间内被交换到相应的位置，要么因为是空格而保持不动

空间复杂度：$O(1)$ ，因为不需要开辟额外的数组

# Method 2: 双指针（使用额外空间）

开辟一个新字符串。从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词并得到单词的起止位置。随后，将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串。

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)$ ，其中 $N$ 为字符串的长度。原字符串中的每个字符都会在 $O(1)$ 的时间内放入新字符串中

空间复杂度：$O(N)$ ，开辟了与原字符串等大的空间

# 剑指 Offer 05. 替换空格

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成 "%20"

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

提示：

• $0 \le$ s.length $\le 10000$

# Method 1: 遍历添加

遍历字符串 s 中的每个字符，如果不是空格，直接赋值给新字符串；否则，赋值 “%20” 到新字符串

string replaceSpace(string s) {

    int i = 0;

    string ans = "";

    while (i < s.size()) {

        if (isspace(s[i])) ans += "%20"; // 等价于 ans.append ("%20")

        else ans += s[i];                // 等价于 ans.push_back (s [i])

        i++;

    }

    return ans;

}

其中， string 的成员函数：

• append() ：向后加入的是 string 类型

• push_back() ：向后加入的是 char 类型

时间复杂度：$O(n)$，其中，$n$ 为字符串的长度

空间复杂度：$O(n)$，新建了一个字符串

# Method 2: 原地修改（双指针）

基本思路：先统计整个字符串中的空格数目，然后把字符串大小扩充为替换后的大小，用 双指针 方法 从右向左 移元素

解题步骤：

1. 统计空格数量 count

2. 修改 s 长度：将所有空格都替换成 "%20" 后，新字符串应比原字符串长 2 * count

3. 定义指针 left 指向原字符串尾部元素， right 指向新字符串尾部元素

4. 从右向左遍历修改 s ，当 left == right 时（代表左边已没有空格）结束循环

   • 当 s[left] 不是空格时，执行 s[right] = s[left]

   • 当 s[left] 是空格时，将区间 [right - 2, right] 内的元素修改为 "%20"

代码实现：

string replaceSpace(string s) {

    // 统计空格数量

    int count = 0;

    for (auto c : s)

        if (c == ' ') count++;

    // 扩充字符串长度

    int oldSize = s.size(), newSize = oldSize + 2 * count;

    s.resize(newSize);

    // 双指针法

    int left = oldSize - 1, right = newSize - 1;

    while (left < right) {

        if (s[left] == ' ') {

            s[right--] = '0';

            s[right--] = '2';

            s[right--] = '%';

            left--;

        }

        else

            s[right--] = s[left--];

    }

    return s;

}

时间复杂度：$O(n)$，统计空格数量、双指针法修改 s 的时间复杂度均为 $O(n)$

空间复杂度：$O(1)$，由于是原地扩展 s 长度，因此使用 $O(1)$ 额外空间

很多数组 / 字符串填充类的问题，都可以预先扩充数组的大小，然后再从右向左进行操作

这样做有两个好处：

1. 不用申请新数组，降低了空间复杂度
2. 从右向左填充元素，避免了从左向右填充元素带来的 “每次添加元素都要将该位置右边的元素向后移动” 的问题，既降低了时间复杂度，也简化了算法

参考：代码随想录

# 剑指 Offer 58-II. 左旋转字符串

剑指 Offer 58-II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串 "abcdefg" 和数字 2，该函数将返回左旋转两位得到的结果 "cdefgab"。

示例 1：

输入：s = "abcdefg", k = 2
输出："cdefgab"

示例 2：

输入：s = "lrloseumgh", k = 6
输出："umghlrlose"

提示：

• $1 \le$ k $\le$ s.length $\le 10000$

进阶：你能想出一个仅使用常数空间的原地操作算法吗？

# 思路

解题思路：

1. 将整个字符串 s 反转
2. 将前 s.size() - n 个字符反转
3. 将后 n 个字符反转

以 s = "abcdefg" ， n = 2 为例：

• 反转整个字符串，得到："gfedcba"
• 反转前 5 个字符串，得到："cdefgba"
• 反转后 2 个字符串，得到："cdefgab"

# Method: 双指针

采用双指针法实现字符串的反转

代码实现：

void reverse(string &s, int left, int right) {

    while (left < right)

        swap(s[left++], s[right--]);

}

string reverseLeftWords(string s, int n) {

    reverse(s, 0, s.size() - 1);

    reverse(s, 0, s.size() - n - 1);

    reverse(s, s.size() - n, s.size() - 1);

    return s;

}

时间复杂度：$O(N)$，其中，$N$ 为字符串长度

空间复杂度：$O(1)$