剑指Offer 05: 替换空格

[songyy5517]

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

分析 这道题考察的是字符串遍历。我们首先扫描字符串中的空格，然后根据空格数量创建新字符数组，再将字符串中的字符转换到新字符数组中即可。

[songyy5517]

思路1：字符串数组

1. 异常处理；
2. 先计算出字符串的空格数，然后创建替换后大小的字符数组；
3. 设置两个指针 p1 和 p2 ，p1指向原字符串长度的位置，p2指向新字符数组的末尾； （1）当 p1 的位置不为空格时，将 p1 位置的字符复制到 p2 位置，p1 和 p2同时向前移动一个位置； （2）当 p1 的位置为空格时，p1向后移动一个位置，p2 当前位置以及后两个位置的字符分别设为 '0', '2', '%' , p2 再向前移动3个位置；
4. 重复上述操作直至 p1等于p2；
5. 将字符数组转换成字符串，并返回。

思路2：StringBuilder截取

1. 异常处理；
2. 创建StringBuilder；
3. 遍历字符串，并进行以下操作： （1）若当前字符等于空格，则向StringBuilder中加入"20%"； （2）若不为空格，则将原字符直接加入StringBuilder中。
4. 将StringBuilder转换成String，并返回。

复杂度分析

• 时间复杂度： $O(N)$ ，我们需要对字符串进行两次/一次遍历，使用 $O(N)$ 时间；
• 空间复杂度： $O(N)$ ，为新字符串额外创建了空间，大小为 $O(N)$ 。

[songyy5517]

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 10:44-10:59
     * @param s string字符串 
     * @return string字符串
     */
    public String replaceSpace (String s) {
        // write code here
        // 分析：遍历字符串
        // 1. 异常
        if (s == null || s.length() == 0)
            return "";

        // 2. 统计空格个数
        int num_sp = 0;
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) == ' ')
                num_sp ++;
        }

        // 3. 为新字符串开辟空间
        char[] new_str = new char[s.length() + 2 * num_sp];

        // 4. 从后往前遍历字符串
        int idx = new_str.length - 1;
        for (int i = s.length() - 1; i >= 0; i--){
            if (s.charAt(i) == ' '){
                new_str[idx] = '0';
                new_str[idx-1] = '2';
                new_str[idx-2] = '%';
                idx -= 3;
            }
            else {
                new_str[idx] = s.charAt(i);
                idx --;
            }
        }

        return new String(new_str);
    }
}

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 10:44-10:59
     * @param s string字符串 
     * @return string字符串
     */
    public String replaceSpace (String s) {
        // write code here
        // 分析：遍历字符串
        // 1. 异常
        if (s == null || s.length() == 0)
            return "";

        // 2. 创建StringBuilder
        StringBuilder new_str = new StringBuilder();

        // 4. 遍历字符串
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) == ' ')
                new_str.append("%20");
            else
                new_str.append(s.charAt(i));
        }

        return new_str.toString();
    }
}

[songyy5517]

2020-05-02 2023/1/5 2023/11/27

• char[]转换成String：new String(char_arr)
• StringBuilder方法