题解 | #替换空格#
替换空格
http://www.nowcoder.com/practice/0e26e5551f2b489b9f58bc83aa4b6c68
算法思想一：辅助栈
解题思路：
借助栈存储字符，遇到空格是则入栈 '%20' ，直到字符串入栈结束
图解：
代码展示:
Python版本
class Solution:
def replaceSpace(self , s ):
# write code here
stack = []
for c in s:
# 将空格替换 '%20' 并入栈
if c == ' ':stack.append('%20')
# 非空正常入栈
else: stack.append(c)
# 以字符串形式返回
return ''.join(stack) 复杂度分析：
时间复杂度O(N)：N表示字符串长度
空间复杂度O(N)：辅助栈空间
算法思想二：遍历法
解题思想：
由于每次替换从 1 个字符变成 3 个字符，使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的 3 倍，这样可保证字符数组可以容纳所有替换后的字符。
1、获得 s 的长度 length
2、创建字符数组 array，其长度为 length * 3
3、初始化 size 为 0，size 表示替换后的字符串的长度
4、从左到右遍历字符串 s
4.1、获得 s 的当前字符 c
4.2、如果字符 c 是空格，则令 array[size] = '%'，array[size + 1] = '2'，array[size + 2] = '0'，并将 size 的值加 3
4.3、如果字符 c 不是空格，则令 array[size] = c，并将 size 的值加 1
1、获得 s 的长度 length
2、创建字符数组 array，其长度为 length * 3
3、初始化 size 为 0，size 表示替换后的字符串的长度
4、从左到右遍历字符串 s
4.1、获得 s 的当前字符 c
4.2、如果字符 c 是空格，则令 array[size] = '%'，array[size + 1] = '2'，array[size + 2] = '0'，并将 size 的值加 3
4.3、如果字符 c 不是空格，则令 array[size] = c，并将 size 的值加 1
5、遍历结束之后，size 的值等于替换后的字符串的长度，从 array 的前 size 个字符创建新字符串，并返回新字符串
代码展示：
JAVA版本
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return string字符串
*/
public String replaceSpace (String s) {
// write code here
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);
return newStr;
}
} 复杂度分析：
时间复杂度O(N)：N表示字符串长度
空间复杂度O(N)：辅助数组空间
算法思想三：函数法
解题思路：
简单暴力，直接调用Python中字符串函数 replace
代码展示：
Python版本
class Solution:
def replaceSpace(self, s):
return s.replace(' ', '%20') 复杂度分析：
时间复杂度O(1)：Python内置算法时间
空间复杂度O(1)：不需要额外空间
