😀前言
在字符串处理中，经常会遇到需要替换特定字符的情况。本文将介绍一道经典的字符串替换问题：将字符串中的空格替换成 “%20”。我们将探讨一种高效的解决方法，通过倒序遍历字符串来实现原地替换，避免额外空间的开销。

🏠个人主页：尘觉主页

替换空格

题目链接

牛客网

题目描述

将一个字符串中的空格替换成 “%20”。

Input:
"A B"

Output:
"A%20B"

解题思路

① 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。

② 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。

③ 当 P2 遇到 P1 时（P2 <= P1），或者遍历结束（P1 < 0），退出。

public String replaceSpace(StringBuffer str) {
    int P1 = str.length() - 1;
    for (int i = 0; i <= P1; i++)
        if (str.charAt(i) == ' ')
            str.append("  ");

    int P2 = str.length() - 1;
    while (P1 >= 0 && P2 > P1) {
        char c = str.charAt(P1--);
        if (c == ' ') {
            str.setCharAt(P2--, '0');
            str.setCharAt(P2--, '2');
            str.setCharAt(P2--, '%');
        } else {
            str.setCharAt(P2--, c);
        }
    }
    return str.toString();
}

代码分析

为了解决这个问题，我们可以采用一种从后向前替换的策略。这种策略的好处在于，从后向前替换可以避免频繁地移动字符，从而减少时间复杂度。具体的解题思路如下：

计算空格数目: 首先遍历一遍原字符串，统计其中的空格数目。这样可以计算出替换之后的字符串的长度。

从后向前替换: 设定两个指针P1和P2，分别指向原字符串的末尾和新字符串的末尾。从后向前遍历原字符串，当P1指向的字符不是空格时，将其复制到P2指向的位置；当P1指向的字符是空格时，将"%20"逆序复制到P2指向的位置。

复杂度分析: 由于字符串的长度可能会增加，因此这种解法的时间复杂度为O(N)，其中N为字符串的长度。同时，由于是在原字符串上进行操作，因此空间复杂度为O(1)。

😄总结

本文介绍了一种将字符串中的空格替换成 “%20” 的解决方法。通过从字符串末尾开始遍历，逐步替换空格，从而实现原地替换而不需额外空间。这种方法的时间复杂度为 O(n)，其中 n 为字符串的长度。通过这种方法，我们可以高效地解决类似的字符串替换问题，提高程序的性能和效率。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞