题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题1，不考虑时间空间复杂度，暴力解题
暴力的解题思路很简单，你可能会想到：有空格的时候直接换成"%20"就行了呗。
public class Solution { public String replaceSpace(StringBuffer str) { String s = ""; for (int i = 0; i <str.length() ; i++) { if(str.charAt(i)==' ') s = s+"%20"; else s = s + str.charAt(i); } return s; } }
解题2
看到解题1，可能会认为很简单，测试结果也对，但是并不是这样子的。
题目是替换空格，那就是在原来的基础上进行替换，而不是重新组合。
来自比特蛋哥：
//字符串操作问题 //解决思路: //虽然是替换问题,但是生成的字符串整体变长了. //因替换内容比被替换内容长,所以,一定涉及到字符串中字符的移动问题 //移动方向一定是向后移动,所以现在的问题无非是移动多少的问题 //因为是 ' ' -> "%20",是1换3,所以可以先统计原字符串中空格的个数(设为n),然后可以计算出新字符串的长度 //所以:new_length = old_length + 2*n //最后,定义新老索引(或者指针),各自指向新老空间的结尾,然后进行old->new的移动 //如果是空格,就连续放入“%20”,其他平移即可。 //当然,C++和Java都有很多容器,也可以从前往后通过开辟空间来进行解决。也就是使用空间来换取时间。 //但是,我们最好不要在当前场景下这么做
public class Solution { public String replaceSpace(StringBuffer str) { //统计出来有多少个空格 int n = 0; for (int i = 0; i <str.length() ; i++) { if(str.charAt(i)==' ') n++; } //设置新的字符串的长度 int new_len = str.length()+(n*2); //计算出来新的字符串的长度 int old_end = str.length()-1; //旧字符串索引最后一个有效位置 int new_end = new_len-1; //新字符串索引最后一个有效位置 str.setLength(new_len);//设置字符串新的长度大小，防止越界 while (old_end>=0 && new_end>=0){ //如果当前位置是空格 if(str.charAt(old_end)==' '){ //就从当前空格的位置往后移动进行替换 str.setCharAt(new_end--,'0'); str.setCharAt(new_end--,'2'); str.setCharAt(new_end--,'%'); --old_end; }else { //当前位置不是空格，就平移 str.setCharAt(new_end--,str.charAt(old_end--)); } } return str.toString(); } }
