剑指Offer05.替换空格
目录
- 剑指Offer05.替换空格
- 题目描述
- 解法一:遍历添加
- 解法二:原地修改
题目描述
请实现一个函数,把字符串s
中的每个空格都替换成“%20”。
解法一:遍历添加
由于每次替换都要把一个空格字符变成三个字符,所以我们可以选择使用字符数组方便地进行替换
建立字符数组的长度为s
字符串长度的3倍,这样可以保证就算字符串全是空格,也可以容纳所有替换后的字符串
过程如下
- 1、获得字符串
s
的长度length - 2、创建字符数组
arr
,长度为length*3
- 3、初始化
size
为0
,size
表示替换后的字符串长度 - 4、从左到右遍历字符串
s
- 获得当前
s
的当前字符c
- 如果字符
c
是空格,则令arr[size]='%',arr[size+1]='2',arr[size+2]=0
,并将size
的值加3 - 如果字符
c
不是空格,则令arr[size]=c
,并将size
的值加1
- 获得当前
- 5、遍历结束后,
size
的值等于替换后的字符串的长度,从arr
的前size
个字符创建新字符串,并返回
public String replaceSpace(String s) {int length = s.length();char[] arr = new char[length*3];int size = 0;for(int i=0;i<length;i++){char c = s.charAt(i);if(c==' '){arr[size++]='%';arr[size++]='2';arr[size++]='0';}else{arr[size++] = c;}}return new String(arr,0,size);}
解法二:原地修改
在解法一中,我们需要额外使用一个数组空间,这样导致我们的空间复杂度为O(n)
我们思考一种不需要额外空间的方法,很明显,我们需要使用双指针
在使用双指针之前,我们需要先扩充一下原字符串的长度
算法过程如下:
- 1、初始化:记录空格数量
count
,字符串s
的长度length
- 2、统计空格数量:遍历
s
,遇到空格则count++
- 3、修改字符串
s
的长度:添加完%20后的字符串长度应为length+2*count
- 4、倒序遍历修改:
i指针
指向原字符串的末尾,j指针
指向新字符串的末尾,当i==j
时跳出循环- 当
s[i]
不为空格时,执行s[i]=s[j]
- 当s[i]为空格时,将字符串闭区间[j-2,j]的元素修改为“%20”,同时j-=2;
- 当
- 5、返回已经修改好的字符串
public String replaceSpace(String s) {//判空进行剪枝操作if(s==null||s.length()==0){return s;}//给字符扩充空间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);}