题目
题目来源leetcode
leetcode地址：剑指 Offer 05. 替换空格，难度：简单。
题目描述(摘自leetcode)：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例 1： 输入：s = "We are happy." 输出："We%20are%20happy." 限制： 0 <= s 的长度 <= 10000
本地调试代码：
class Solution { public String replaceSpace(String s) { ... } public static void main(String[] args) { System.out.println(new Solution().replaceSpace("We are happy.")); } }
题解
NO1：双指针（最优解，O(n)）
思路： 对于字符串中空格=>"%20"，由一个字符填充为3个字符，普通解法就是遍历一遍的过程中遇到空白字符串先将后面的统一移动两个接着进行填充，该思路时间复杂度为O(n2)；
所以这里我们使用双指针的方案，首先遍历一遍字符串确定其中有多少个空格对原始字符串进行扩容，紧接着来定义两个指针，一个指针指向原始字符串最后一个位置，另一个指针指向扩展之后最后一个位置，每次移动两个指针同时向前移动，若是左指针碰到空格，右指针进行%、0、2向前以前填充前进两步；若不是空格，右指针指向的值改为左指针当前指向的值，根据此规则不断重复即可！时间复杂度为O(n)。这里我直接引用 代码随想录—题目：剑指Offer 05.替换空格 中的思路图，十分推荐该博主的算法指南，十分清晰
代码：
public String replaceSpace(String s) { //扩充空间，空格数量2倍 StringBuilder str = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if(s.charAt(i) == ' '){ str.append(" "); } } //若是没有空格直接返回 if(str.length() == 0){ return s; } //有空格情况 定义两个指针 int left = s.length() - 1;//左指针：指向原始字符串最后一个位置 s += str.toString(); int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置 char[] chars = s.toCharArray(); while(left>=0){ if(chars[left] == ' '){ chars[right--] = '0'; chars[right--] = '2'; chars[right] = '%'; }else{ chars[right] = chars[left]; } left--; right--; } return new String(chars); }
