刷题剑指Offer05-替换空格

题目

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例 1： 输入：s = "We are happy."输出："We%20are%20happy.

---

思路

要把字符串中的空格替换成%20，首先就是在原有的字符数组里扩容，相当于每个空格再额外扩大两个空格的位置。然后通过双指针的方法，将i指针指向未扩容的数组末尾，j指针指向扩容后的数组末尾，然后从后往前填充。如果从前往后填充的话，每次添加元素都要将添加元素之后的所有元素向后移动，增加了时间复杂度为O(n^2)。

class Solution { public String replaceSpace(String s) { if(s == null || s.length() == 0){ return s; } //扩充空间，空格数量的2倍 StringBuilder str = new StringBuilder(); //StringBuilder是对字符串本身进行修改的类 for(int i = 0; i < s.length(); i++){ if(s.charAt(i) == ' '){ //charAt(i)方法用来返回i索引处的字符 str.append(" "); } } //若是没有空格，则直接返回 if(str.length() == 0){ return s; } //有空格情况 定义两个指针 int left = s.length() - 1; //指向原始字符串最后一个位置 s += str.toString(); //在原字符串的基础上扩容（2倍的空格字符大小） int right = s.length() - 1; //指向扩容后字符串的最后一个位置 char[] chars = s.toCharArray(); //将字符串s转成字符数组 while(left >= 0){ if(chars[left] == ' '){ chars[right--] = '0'; chars[right--] = '2'; chars[right] = '%'; }else{ chars[right] = chars[left]; } left--; right--; } return new String(chars); } }

转载至《代码随想录》