剑指 Offer 05. 替换空格

题目地址：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/

题目主要信息：

• 把字符串 s 中的每个空格都替换成"%20"

一、String的字符替换API

public class Solution {

    public static void main(String[] args) {
        String s = "We are happy.";
        System.out.println(new Solution().replaceSpace(s));
    }

    public String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }

}

复杂度分析：

String的replaceAll()方法的底层使用了StringBuffer，对字符串遍历，通过StringBuffer的append()方法进行拼接。

• 因为底层遍历了字符串，所以时间复杂度为 $O(n)$

• 产生了新的字符串，空间复杂度为 $O(n)$

二、使用StringBuilder的字符串拼接API

public class Solution {

    public static void main(String[] args) {
        String s = "We are happy.";
        System.out.println(new Solution().replaceSpace(s));
    }

    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ' '){
                sb.append("%20");
            }else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

}

复杂度分析：

• 因为遍历字符串，所以时间复杂度是O(n)
• 产生了新的字符串，空间复杂度为O(n)

分析：在单线程情况下，使用StringBuilder的效率 比 使用String的replaceAll() 方法 ( replaceAll()的底层用了StringBuffer ) 的效率高。因为单线程情况下，StringBuilder的效率比StringBuffer的效率高。