题目链接：剑指 Offer 05. 替换空格

解题思路：重构字符串

在 Java 语言中，字符串为不可变的，所以如果使用 Java 语言，我们就无法实现原地修改。

我们可以使用一个新的字符串，在遍历题目给定的字符串 “s” 时，遇到字符 ‘ ‘ ，即替换成 “%20” 添加至我们构建的新字符串中。

如果直接使用 String 类来构建字符串，那么每次添加一个字符都会创建一个新的 String 对象，所以，我们可以使用 StringBuilder 。

Java 提供了 StringBuilder 类，在重构字符串时，可以不产生新的字符串对象，大大提高了效率并且节省了空间。

代码

Java

  1. class Solution {
  2.     public String replaceSpace(String s) {
  3.         StringBuilder sb = new StringBuilder();
  5.         for(int i = 0; i < s.length(); i++){
  6.             if(s.charAt(i) == ' '){
  7.                 sb.append("%20");
  8.             }else {
  9.                 sb.append(s.charAt(i));
  10.             }
  11.         }
  12.         return sb.toString();
  13.     }
  14. }

复杂度分析

  • 时间复杂度：O(N)
    遍历一遍字符串，为 O(N)
  • 空间复杂度：O(N)
    StringBuilder 使用了线性大小的额外空间