【剑指offer】面试题5：替换空格

向右看齐 2022-06-12 02:15 159阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

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

## 思路 ##

方法1：用split进行分割，然后用StringBuilder再进行组合  
这样做的话时间复杂度O(n)，空间复杂度O(n)  
方法2：先遍历字符串，统计出字符串中空格的总数。因为空格要换成%20，所以可以计算出替换后的字符串的总长度，新字符串总长度=原字符串+2\*空格个数。**然后从字符串的后面开始复制和替换。**  
这样做的话时间复杂度为O(n)，空间复杂度为O(1)

## 代码（使用方法2） ##

public static String replaceSpace(StringBuffer str) {
            int oldLen = str.length();
            int len = oldLen;
            for(int i = 0; i < str.length(); ++i) {
                if(str.charAt(i) == ' ')
                    len += 2;
            }
            str.setLength(len);
    
            for(int i = oldLen - 1, j = len - 1; i >= 0; ) {
                if(str.charAt(i) == ' ') {
                    str.setCharAt(j--, '0');
                    str.setCharAt(j--, '2');
                    str.setCharAt(j--, '%');
                    --i;
                }
                else {
                    str.setCharAt(j--, str.charAt(i--));
                }
            }
            return str.toString();
        }

## 测试 ##

public static void main(String[] args) {
            test1();
            test2();
            test3();
        }
    
        /**
         * 输入的字符串中包含空格
         * 1.空格位于字符串的最前面
         * 2.空格位于字符串的最后面
         * 3.空格位于字符串的中间
         * 3.字符串中有连续多个空格
         */
        private static void test1() {
            StringBuffer sb = new StringBuffer(" lin");
            String str = _05_ReplaceSpaces.replaceSpace(sb);
            MyTest.equal(str, "%20lin");
    
            sb = new StringBuffer("lin ");
            str = _05_ReplaceSpaces.replaceSpace(sb);
            MyTest.equal(str, "lin%20");
    
            sb = new StringBuffer("l in");
            str = _05_ReplaceSpaces.replaceSpace(sb);
            MyTest.equal(str, "l%20in");
    
            sb = new StringBuffer("  l  in  ");
            str = _05_ReplaceSpaces.replaceSpace(sb);
            MyTest.equal(str, "%20%20l%20%20in%20%20");
        }
    
        /**
         * 输入的字符串没有空格
         */
        private static void test2() {
            StringBuffer sb = new StringBuffer("lin");
            String str = _05_ReplaceSpaces.replaceSpace(sb);
            MyTest.equal(str, "lin");
        }
    
        /**
         * 特殊输入测试
         * 1.字符串长度为0
         * 2.字符串只有一个空格
         * 3.字符串中只有连续多个空格
         */
        private static void test3() {
            StringBuffer sb = new StringBuffer("");
            String str = _05_ReplaceSpaces.replaceSpace(sb);
            MyTest.equal(str, "");
    
            sb = new StringBuffer(" ");
            str = _05_ReplaceSpaces.replaceSpace(sb);
            MyTest.equal(str, "%20");
    
            sb = new StringBuffer("   ");
            str = _05_ReplaceSpaces.replaceSpace(sb);
            MyTest.equal(str, "%20%20%20");
        }

[Link 1]: https://github.com/linpeiyou/CodingInterviews