python练习:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符
程序员文章站
2022-03-03 22:03:43
题目输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.”和”aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.”。第一种思路直接通过遍历,我们依次判定第一个字符串中是否存在第二个字符串中的第 i 个字符。如果存在,则删除该字符。该方法的时间复杂度为O(n^2)。代码def DeleteString(str1, str2): if str1 is None or str2 is None:...
题目
输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.”和”aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.”。
第一种思路
直接通过遍历,我们依次判定第一个字符串中是否存在第二个字符串中的第 i 个字符。如果存在,则删除该字符。该方法的时间复杂度为O(n^2)。
代码
def DeleteString(str1, str2):
if str1 is None or str2 is None:
return
for i in str1:
if i in str2:
str1 = str1.replace(i, '') # 进行字符替换
return ''.join(str1)
if __name__ == '__main__':
print(DeleteString("They are students", "aeiou"))
print(DeleteString("With the development of AI, high-dimensional data", "aeiou"))
运行结果为:
Thy r stdnts
Wth th dvlpmnt f AI, hgh-dmnsnl dt
第二种思路
以空间换时间。我们可以创建一个用数组实现的简单哈希表来存储第二个字符串。
对于字符串,由于 ASCII 码的所有符号为256个。那么,我们可以申请一个数组用来代表这256个字符是否存在于第二个字符串中。如果有,则标记为1;如果没有,则标记为0。
那么,我们从头到尾扫描第一个字符串中的每一个字符时,使用O(1)的时间就能读取出该字符对应哈希表中的 ASCII 值。如果值为1,说明它存在于第二个字符串中,就需要删除。如果第一个字符串长度是n,那么总的时间复杂度为O(n)。
代码
def DeleteString(str1, str2):
if str1 is None or str2 is None:
return
hashTable = [0] * 256 # 初始化哈希表,以数组形式展现
for i in str2:
hashTable[ord(i)-ord('a')] = 1 # 使用ord()将字符转换为数字索引
for i in str1:
if hashTable[ord(i)-ord('a')] == 1: # 查询i字符是否在哈希表中已存在
str1 = str1.replace(i, '') # 进行字符替换
return str1
if __name__ == '__main__':
print(DeleteString("They are students", "aeiou"))
print(DeleteString("With the development of AI, high-dimensional data", "aeiou"))
运行结果为:
Thy r stdnts
Wth th dvlpmnt f AI, hgh-dmnsnl dt
本文地址:https://blog.csdn.net/wumenglu1018/article/details/107677016