替换空格

题目出处

• 剑指 Offer - 5 - 替换空格
• NowCoder

替换空格

1 题目描述

请实现一个函数，将一个字符串中的每个空格替换成 %20。例如，当字符串为We Are Happy，则经过替换之后的字符串为We%20Are%20Happy。

Input:
"A B"

Output:
"A%20B"

2 解题思路

有在原字符串上替换，和创建新字符串两种操作。

思路一：O(n²) 的解法

从前往后插入。这样移动的次数多，不建议

思路二：O(n) 的解法

从后往前插入。先统计出字符串中空格总数，计算出替换之后字符串的总长度，从后向前移动。

• 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。
• 令 oldEnd 指向字符串原来的末尾位置，newEnd 指向字符串现在的末尾位置。oldEnd 和 newEnd 从后向前遍历，当 oldEnd 遍历到一个空格时，就需要令 newEnd 指向的位置依次填充 02%（注意是逆序的），否则就填充上 oldEnd 指向字符的值。从后向前遍是为了在改变 newEnd 所指向的内容时，不会影响到 oldEnd 遍历原来字符串的内容。
• 当 newEnd 遇到 oldEnd 时（newEnd <= oldEnd），或者遍历结束（oldEnd < 0），退出。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        if(null == str){
            return "";
        }
        
        int oldEnd = str.length() - 1;
        for (int i = 0; i <= oldEnd; i++){
            if (str.charAt(i) == ' '){
                str.append("  ");
            }
        }
        
        int newEnd = str.length() - 1;
        while (oldEnd >= 0 && newEnd > oldEnd) {
            char c = str.charAt(oldEnd--);
            if (c == ' ') {
                str.setCharAt(newEnd--, '0');
                str.setCharAt(newEnd--, '2');
                str.setCharAt(newEnd--, '%');
            } else {
                str.setCharAt(newEnd--, c);
            }
        }
        return str.toString();
    }
}

3 举一反三

在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）则需要重复移动数字（或字符）多次，那么可以考虑从后往前复制，从而减少移动次数，提高效率。