欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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