offer05.java

/**
 * [05] 替换空格
 *
 * 题目：将给定字符串 s 中的每个空格都替换成 "%20"。
 *
 * 思路：1。初始化一个 StringBuilder，遍历字符串，当前字符为 ' ' 时，向 StringBuilder 中加入 "%20"；当前字符不为 ' ' 时，
 *         向 StringBuilder 中加入该字符。
 *
 *      其实原题想考察的是：给定一个包含空格的字符数组，将数组中的空格替换为 "%20" 三个字符，要求额外空间复杂度为 O(1)。
 *      （假设数组中有足够的的空间来保存新添加的字符）
 *      因为要求额外空间复杂度为 O(1)，所以就在原字符数组上进行操作：
 *      2。从前往后遍历字符串，每次遇到空格时需要先将空格后的字符全部后移两个字节，再将空格替换为 "%20"。时间复杂度：O(n ^ 2)。
 *      3。令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要
 *         令 P2 指向的位置依次填充 "20%" （注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容
 *         时，不会影响到 P1 遍历原来字符串的内容。这样就避免多次重复移动字符。
 */
class Solution {
    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public String replaceSpace1(String s) {
        StringBuilder sb = new StringBuilder();
        for (char chr : s.toCharArray()) {
            if (chr == ' ') {
                // replace all ' ' with "%20".
                sb.append("%20");
            } else {
                sb.append(chr);
            }
        }

        return sb.toString();
    }
}