替换空格

2017-12-22

问题描述
请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。
分析
暴力
找到空格就进行替换，按到常理的思路是按照从前往后的顺序题替换，这样每替换一次就要移动元素一次，故时间是O(n^2)
从后往前
刚读到题目的时候就想起来从后往前这个思路，因为可以减少移动元素的次数，通过一次遍历就可以完成元素的替换。之前写过一个两个有序表合成一个新的有序表的时候用的也是这样的思路。
Python小记

Python对字符串进行扩容，我也不知道如何定义指定大小的字符串，Python中有一些函数可以直接扩容，比如str.center(size)或者是str.zfill(size)，但这两个一个是居中填充，一个是左边填充0，可是这次需要右边填充，就写了一个函数。
1
2
3
4
5
6
#左填充size个大小，填充的是空格符号
t = " "
i = 1
while(i <= size):
string += t
i += 1
Python不支持对字符串通过下标进行修改，比如在C中可以这样写
1
2
char c[200] = "hello world"
c[5] = 'N'

然而Python中不可以这样写，权限是可读不可写，故通过切片来解决这个问题

1
2
3

#string为待修改字符，index为需要修改下标，比如就像上面的20，char被修改的字符，像上面的'N'
def replace(string, index, char):
	return string[:index] + char + string[(index + 1):]

Python竟然没有++运算符，吐槽一下
Python实现

# coding:-utf-8

# py不支持对字符串按照下标直接修改值
# 因此写了这个函数用来直接修改字符串
# 中某个下标的值
def replace(string, index, new):
	return string[:index] + new + string[(index + 1):]	

def replacespace(string):
	if(len(string) == 0):
		return False
	#统计原字符串长度
	original = len(string)
	#统计空格出现次数
	blank = string.count(" ")
	#计算新字符串长度	
	new = original + blank * 2
	#扩充字符串的大小	
	t = " "
	i = 1
	while(i <= blank * 2):
		string += t
		i += 1
	#Py的下标都是从0开始
	original -= 1
	new -= 1
	while(original >= 0 and new > original):
		if(string[original] == " "):
			string = replace(string, new, '0')
			new -= 1
			string = replace(string, new, '2')
			new -= 1
			string = replace(string, new, '%')
			new -= 1
		else:
			string = replace(string, new, string[original])
			new -= 1
		original -= 1
	
	return string

def test(s):
	expected = s.replace(" ", "%20")
	result = replacespace(s)
	if(expected == result):
		print "passed"
	else:
		print "failed"

def test1():
	test("hello world")

def test2():
	test(" helloworld")

def test3():
	test("helloworld ")

def test4():
	test("hello  world")

def test5():
	test("")

def test7():
	test(" ")

def test8():
	test("helloworld")

def test9():
	test("     ")

test1()
test2()
test3()
test4()
test5()
test7()
test8()
test9()