Update 替换空格.py

wangershi · web-flow · commit 85dea78ce6e6 · 2017-11-06T19:39:27.000+08:00
replace1方法和replace2方法都是O(n*m)的时间复杂度，这里m是空格的数量，因为list的insert是一个O(n)的复杂度。
而list的append是一个O(1)的时间复杂度，除了扩容时的时间损耗，append方法只需要遍历一次数组即可得结果。
diff --git a/Target Offer/替换空格.py b/Target Offer/替换空格.py
@@ -6,6 +6,20 @@
 # -*- coding:utf-8 -*-
 class Solution:
     # s 源字符串
+    
+    # 使用append一次遍历即可替换
+    # 由于list的append是O(1)的时间复杂度，除了扩容所导致的时间损耗，该算法复杂度为O(n)
+    def replaceSpaceByAppend(self, s):
+        string = list(string)
+	    stringReplace = []
+	    for item in string:
+		    if item == ' ':
+			    stringReplace.append('%')
+			    stringReplace.append('2')
+			    stringReplace.append('0')
+		    else:
+			    stringReplace.append(item)
+	    return "".join(stringReplace)
 
     # 创建新的字符串进行替换
     def replaceSpace1(self, s):
