字符串替换
一、字符串的替换【倒着复制】
原问题思路：
-
- 遍历第一遍：得到两个信息，chas的左半区有多大，记为len，左半区的空格有多少，记为num。
可知最终长度为len+2*num，替换字母为%20.
-
- 从右往左遍历第二遍：遇到字母复制到新长度最后位置，遇到空格则加入02%。
原问题代码：
def changeStr(s): if not s: return s count = 0 n = len(s) for i in range(n): if s[i] == ' ': count += 1 m = n + count * 2 s += '0'*(count*2) j = 0 for i in range(n-1,-1,-1): tmp = m - j -1 if s[i] != ' ': s = s[:tmp] + s[i] + s[tmp+1:] j += 1 else: s = s[:tmp-2]+'%20'+s[tmp+1:] j += 3 return s s = 'AB C DEF G' print(changeStr(s))
二、移动字符【倒着复制】
补充问题思路：
从右往左倒着复制，遇到数字直接复制，遇到*不复制，当把所有数字复制完，把左半区全部设置成*即可。
代码：
def sortStr(s): if not s: return s j = 0 n = len(s) for i in range(n-1,-1,-1): tmp = i + j if s[i] != '*': s = s[:tmp] + s[i] + s[tmp+1:] else: j += 1 s = '*'*j + s[n-j-1:] return s s = '123**24**2*' print(sortStr(s))
三、替换字符串中连续出现的指定字符串
六、替换字符串中连续出现的指定字符串
给定三个字符串str、from和to，已知from字符串中无重复字符，把str中所有from的子串全部替换成to字符串，对连续出现from的部分要求只替换成一个to字符串，返回最终的结果字符串
举例：
str="123abc"，from="abc"，to="4567"，返回"1234567"
str="123"，from="abc"，to="456"，返回"123"
str="123abcabc"，from="abc"，to="X"，返回"123X"
思路：
先将str中含from的都替换成0*len(from)，然后将不等于0的用cur暂存，遇到0则 res + cur + to。
把str看作字符类型的数组，首先把str中from部分所有位置的字符编码设为0（即空字符），如"12abcabca4"，from="abc"，处理后str=['1','2',0,0,0,0,0,0,'a','4']。
具体步骤如下：
1 生成整数变量match，标识目前匹配到from字符串的什么位置，初始时match=0；
2 从左到右遍历str中每个字符，假设当前遍历到str[i]；
3 若str[i]==from[match]，若match是from最后一个字符的位置，说明在str中发现了from字符串，则从i位置向前的M个位置，都把字符编码设为0，M为from的长度，设置完成后令match=0；若match不是from最后一个字符的位置，则match++。继续遍历str的下一个字符；
4 若str[i]!=from[match]，说明匹配失败，令match=0，即回到from开头重新匹配。继续遍历str的下一个字符；
代码：
def replace(s,f,to):
if not s or f == None:
return s
arr = list(s)
j = 0
for i in range(len(s)):
if s[i] == f[j]:
if j == len(f)-1:
s = s[:i-j] + '0' * len(f) + s[i+1:]
# s[i-j+1:i+1] = '0' * len(f)
j = 0
else:
j += 1
else:
j = 0
res = ''
cur = ''
for i in range(len(s)):
if s[i] != '0':
cur = cur + s[i]
if s[i] == '0' and (i == 0 or s[i-1] != '0'):
res = res + cur + to
cur = ''
if cur:
res = res + cur
return res
s = '12abcabc3'
f = 'abc'
to = 'X'
replace(s,f,to)
四、去掉字符串中连续出现k个0的子串
给定一个字符串str和一个整数k，如果str中正好有连续的k个'0'字符出现时，把k个连续的'0'字符去除，返回处理后的字符串。
举例：
str="A00B"，k=2，返回"AB"；
str="A0000B000"，k=3，返回"A0000B"。
思路：
采用count记录连续0的个数，若count==k，则将str连续的0删除。
代码：
def removeKzeros(arr,k):
if not arr or k == 0:
return arr
count , i = 0 , 0
while i < len(arr):
if arr[i] != '0':
i += 1
while i < len(arr) and arr[i] == '0':
count += 1
i += 1
if count and count == k:
arr = arr[:i-count]+arr[i:]
count = 0
return arr
arr = 'A00B'
k = 2
removeKzeros(arr,k)
arr="A0000B000"
k=3
removeKzeros(arr,k)