问题
请实现一个函数,把字符串 s 中的每个空格替换成”%20”
示例 1:
输入:s = “We are happy.”
输出:”We%20are%20happy.”
解法一:双指针法
首先扩充数组到每个空格替换成"%20"
之后的大小,然后从后向前替换空格,也就是双指针法
为什么要从后向前填充,从前向后填充不行么?
从前向后填充就是的算法了,因为每次添加元素都要将添加元素之后的所有元素向后移动
class Solution {
public String replaceSpace(String s) {
int count = 0;
int oldSize = s.length();
char[] c = s.toCharArray();
for(int i = 0; i < oldSize; i++){
if(c[i] == ' '){
count++;
}
}
char[] array = new char[oldSize + count * 2];
int newSize = array.length;
for (int i = newSize - 1, j = oldSize - 1; j < i ; i--, j--) {
if (c[j] != ' ') {
array[i] = c[j];
} else {
array[i] = '0';
array[i - 1] = '2';
array[i - 2] = '%';
i -= 2;
}
}
return new String(array);
}
}
输入
"We are happy."
输出
"\u0000\u0000%20are%20happy."
预期结果
"We%20are%20happy."
出错出哪了???
解法二:官方解法
由于每次替换从 1 个字符变成 3 个字符,使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的 3 倍,这样可保证字符数组可以容纳所有替换后的字符
- 获得 s 的长度
length
- 创建字符数组
array
,其长度为length * 3
- 初始化
size
为 0,size
表示替换后的字符串的长度 - 从左到右遍历字符串 s
- 获得 s 的当前字符 c
- 如果字符 c 是空格,则令
array[size] = '%'
,array[size + 1] = '2'
,array[size + 2] = '0'
,并将size
的值加 3 - 如果字符 c 不是空格,则令
array[size] = c
,并将size
的值加 1 遍历结束之后,
size
的值等于替换后的字符串的长度,从array
的前size
个字符创建新字符串,并返回新字符串class Solution { public String replaceSpace(String s) { int length = s.length(); char[] array = new char[length * 3]; int size = 0; for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == ' ') { array[size++] = '%'; array[size++] = '2'; array[size++] = '0'; } else { array[size++] = c; } } String newStr = new String(array, 0, size); //把一个数组array从0取到size return newStr; } }
时间复杂度:
。遍历字符串 s 一遍
- 空间复杂度:
。额外创建字符数组,长度为 s 的长度的 3 倍