【题目描述】
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
【思路】
暴力法:时间复杂度O(n*n),从头到尾遍历字符串,遇到空格就将空格后的所有元素向后移动2位。
改进法:时间复杂度O(n),先从头到尾遍历统计空格数,计算出替换后字符串的长度;而利用双指针,p1指向原字符串尾部,p2指向新字符串尾部,利用一个迭代,从尾向迭代终止条件是p1=0,头移动两个指针,当p1遇到非空格时,将p1所指字符复制给p2位置;当p1遇到空格时,将%20给p2位置,p2相应的向前移动3位;
【代码】
PYTHON:
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
count= 0
for string in s:
if string==' ':
count+= 1
len_b=len(s)+count* 2
p1,p2=len(s)-1,len_b-1
re=['0']*len_b
while p1>=0:
if s[p1]!= ' ':
re[p2]=s[p1]
p2-= 1
else:
re[p2]='0'
re[p2-1]='2'
re[p2-2]='%'
p2-=3
p1-=1
return ''.join(re)
C++:
class Solution {
public:
void replaceSpace(char str[],int length) {
int count=0;
int i=0;
int init_length=1;
while(str[i]!='\0'){
if(str[i]==' '){
count++;
}
init_length++;
i++;
}
int new_length=init_length+2*count;
if (new_length>length) exit(1);
while(init_length>0){
new_length--;
init_length--;
if(str[init_length]!=' '){
str[new_length]=str[init_length];
}else{
str[new_length]='0';
str[new_length-1]='2';
str[new_length-2]='%';
new_length-=2;
}
}
}
};
//char *str表示将一个名为str的指针变量,其中存放着一个字符串常量的地址,str的初值是字符串“hello”的地址,通过索引str[i]可访问给定字符串。
//char str[]就表示一个数组,内部存放着chasr类型的常量,长度已提前固定好。