每日一题《剑指offer》字符串篇之替换空格
替换空格
难度:简单
描述
请实现一个函数,将一个字符串s中的每个空格替换成“%20”。
例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
数据范围
数据范围:0≤len(s)≤1000
举例
解题思路
对于这个题目,我们首先想到原来的一个空格替换为三个字符,字符串长度会增加,因此,存在以下两种不同的情况:(1)允许创建新的字符串来完成替换。(2)不允许创建新的字符串,在原地完成替换。
第一种情况比较简单。对于第二种情况,有以下两种解法:
方法一:从头到尾遍历字符串,当遇到空格时,直接利用String类的方法将空格替换成"%20"。时间复杂度为O(n^2)
方法二:申请一个临时数组,然后再遍历这个字符串的每个字符,如果不是空格就把遍历的字符添加到临时数组中,如果是空格就添加3个字符'%','2','0'分别到临时数组中,最后再把临时数组转化为字符串即可。时间复杂度为O(n)。
实现代码(java)
方法一:
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ public String replaceSpace (String s) { // write code here for(int i = 0; i < s.length(); i++){ if(s.charAt(i)==' '){ s = s.replace(" ","%20"); } } return s; } }
方法二:
public String replaceSpace(String s) { int length = s.length(); char[] array = new char[length * 3]; int index = 0; for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == ' ') { array[index++] = '%'; array[index++] = '2'; array[index++] = '0'; } else { array[index++] = c; } } String newStr = new String(array, 0, index); return newStr; }