❓剑指 Offer 05. 替换空格

难度：简单

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

示例 1：

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

限制：

• 0 <= s 的长度 <= 10000

💡思路：双指针法

如果想把这道题目做到极致，就不要只用额外的辅助空间了！

• 首先扩充数组到每个空格替换成" %20 "之后的大小；
• i 指向新长度的末尾，j 指向旧长度的末尾；
• 然后从后向前替换空格，也就是双指针法。

过程如下：

🍁代码：(Java、C++)

Java

class Solution {public String replaceSpace(String s) {if(s.length() == 0 || s == null) return s;StringBuilder str = new StringBuilder();//扩充空间，空格数量2倍for(int i = 0; i < s.length(); i++){if(s.charAt(i) == ' '){str.append("  ");}}if(str.length() == 0) return s;int j = s.length() - 1;//左指针s += str.toString();int i = s.length() - 1;//右指针char[] ch = s.toCharArray();while(j < i){if(ch[j] != ' ') ch[i] = ch[j];else{ch[i--] = '0';ch[i--] = '2';ch[i] = '%';}j--;i--;}return new String(ch);}
}

C++

class Solution {
public:string replaceSpace(string s) {int count = 0; //统计空格的个数for(char c : s){if(c == ' ') count++;}if(count == 0) return s;int n = s.size();s.resize(n + count * 2);for(int j = n - 1, i = n + count * 2 - 1; j < i; i--, j--){//定义左右双指针if(s[j] != ' ') s[i] = s[j];else{s[i--] = '0';s[i--] = '2';s[i] = '%';}}return s;}
};

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$，其中 n 为字符串 s 的长度。
• 空间复杂度：$O(1)$ 或 $O(n)$，取决于使用的语言中字符串类型的性质。如果字符串是可修改的（C++），那么我们可以直接在原字符串上修改，空间复杂度为 $O(1)$，（Java）否则需要使用 $O(n)$ 的空间将字符串临时转换为可以修改的数据结构（例如数组），空间复杂度为 $O(n)$。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！

注： 如有不足，欢迎指正！