剑指Offer_#5_替换空格
Contents
题目
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."限制：
0 <= s 的长度 <= 10000
思路分析
思路
遍历输入字符串s,遇到空格就在结果当中添加"%20",遇到其他的字符就添加字符本身。
方法1：char数组
关键问题在于，不知道字符串s当中有几个空格，那么在定义字符数组的时候无法给出数组的大小。
解决方法：
- 假设最极端情况，也就是输入字符串全都是空格，那么用于存放结果的字符数组长度就是输入字符串长度的3倍。
- 在遍历的过程中增加一个计数器变量，记录字符数组最后一个有效字符的索引，返回之前将有效的部分转换为字符串。
方法2：StringBuilder
使用StringBuilder来存放结果，就避免了上面的问题，不需要给出数组大小。
解答
解答1：char数组
class Solution {
public String replaceSpace(String s) {
char[] charArray = new char[3*s.length()];
int size = 0;
for(int i = 0;i < s.length();i++){
char c = s.charAt(i);
if(c == ' '){
charArray[size++] = '%';
charArray[size++] = '2';
charArray[size++] = '0';
}else{
charArray[size++] = c;
}
}
String newStr = new String(charArray,0,size);
return newStr;
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
解答2：StringBuilder
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder();
int i = 0;
while(i <= s.length() - 1){
if(s.charAt(i) == ' ') res.append("%20");
else res.append(s.charAt(i));
i++;
}
return res.toString();
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)