算法思想一:辅助栈

解题思路:

借助栈存储字符,遇到空格是则入栈 '%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
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):不需要额外空间