我要评论题目
输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论