pythontip 100days-day6

题目

输入为两个字符串str1,str2。找出两个字符串中不同的字符

例子

• None输入 -> None
• ‘abc’,’abcc’ -> ‘c’
• ‘abcd’,’abcde’ -> ‘e’
• ‘aaabbcdd’,’abdbacade’ -> ‘e’

假设

• 两个字符串中只有唯一一个字符不同
• 所有字符均为ascii

tips

1. 统计每个字符出现的次数
2. 利用异或运算

答案

解法1:

def find_diff(str1, str2):
    if str1 is None or str2 is None:
        return None
    count = {}
    for char in str1:
        count[char] = count.get(char,0) + 1
    for char in str2:
        count[char] = count.get(char,0) - 1
    for char,char_count in count.items():
        if char_count != 0:
            return char
    return None            

性能：

1. 时间复杂度O(n)
2. 空间复杂度O(n)

关键点：1.利用dict统计每个字符出现次数

解法2:

def find_diff(str1, str2):
    if str1 is None or str2 is None:
        return None 
    result = 0
    for char in str1:
        result ^= ord(char)
    for char in str2:
        result ^= ord(char)
    return chr(result)

性能：

1. 时间复杂度O(n)
2. 空间复杂度O(1)

关键点:

1. 利用异或运算xor的性质

解法3：

def find_diff_reduce(str1, str2):
    """
    1. 将str1、str2中字符的ASCII码生成为列表
    2. 使用reduce遍历列表元素，并做异或处理
    3. 相同的字符异或后为零，最后的结果转为字符就是不同字符
    :param str1:
    :param str2:
    :return:
    """
    if str1 is None or str2 is None:
        return None
	from functools import reduce
    return chr(reduce(lambda x, y: x ^ y, [ord(x) for x in str1 + str2]))

性能：

1. 时间复杂度O(n)
2. 空间复杂度O(1)

关键点:

1. 利用异或运算xor的性质
2. 使用reduce的特性，接受两个值，上一次的返回结果和下一个值。第一次会把迭代对象的第一个值作为返回值，接受第一个值和第二个值。

解法4：

def find_diff_list(str1, str2):
    """
    1. 将str1、str2转为字符串
    2. 遍历str1，在str2中删除str1中的元素
    3. 将剩下的元素连接成字符串返回
    :param str1:
    :param str2:
    :return:
    """
    if str1 is None or str2 is None:
        return None

    sl1 = list(str1)
    sl2 = list(str2)

    for item in sl1:
        if item in sl2:
            sl2.remove(item)

    return ''.join(sl2)

性能：

1. 时间复杂度O(n)
2. 空间复杂度O(4n)

关键点:

1. 利用列表处理字符串，将字符串转换为列表，遍历列表元素，移除遍历的元素