博客

好久没更(水)博客了，今天有空了来更(水)一下

一


按照我的理解就是 判断两个字符串是否99% 相似，两个字符串只能有一个字符的不同



1.1逐个匹配


我第一想法是逐个字符进行匹配，然后记录两个字符的不同字符数，然后进行判断， 如：

def no_equal(str1, str2):
    nums = 0
    # 记录不同字符列表
    ls_list = []
    # 以str1为主进行匹配，所有str1为最长的那个字符串
    if len(str1) < len(str2):
        str1, str2 = str2, str1
    count = 1
    while 1:
        print("循环{}次".format(count))
        count += 1
        if nums >= len(str1):
            break
        try:
            # 如果循环到两个字符串的同一个下标值不同的时候，
            # 将这个不同值从str1字符串中切割出来，构造出新的str1字符串
            if str1[nums] != str2[nums]:
                # 如果这个下标不为0的时候，就进行正常的切割
                if nums > 0:
                    ls_list.append(str1[nums])
                    str1 = str1[0:nums] + str1[nums + 1:]
                else:
                    # 下标为0，直接切割
                    str1 = str1[1:]
            else:
                # 如果两个字符串相同的下标的数据一样时，nums下标+1
                nums += 1
        except:
            # 有种情况是str1切了多次，长度和str2不匹配了，就来判断两个字符串最后一位是否相同，并结束循环
            if str1[-1] != str2[-1]:
                ls_list.append(str1[-1])
            break
    if len(ls_list) > 1:
        return False
    return True


def equal(str1, str2):
    nums = 0
    # 临时列表，记录两个字符串中不同的字符
    ls_list = []
    count = 1
    while nums < len(str1):
        print("循环{}次".format(count))
        count += 1
        # 如果循环匹配到字符串相同的下标的字符不一样的时候， 就用临时列表记录下来
        if str1[nums] != str2[nums]:
            ls_list.append(str1[nums])
        nums += 1
    #     如果不同字符数量超过了2位，则这两个字符返回False
    if len(ls_list) > 1:
        return False
    return True


def isStringAlike(str1, str2):
    # 如果两个单词字符数相等,调用equal 函数进行操作
    if len(str1) == len(str2):
        return equal(str1, str2)
    # 如果两个字符串的长度差在1之间，调用no_equal 函数进行判断
    elif len(str1) + 1 == len(str2) or len(str1) - 1 == len(str2):
        return no_equal(str1, str2)
    # 字符长度不合适
    return False


print(isStringAlike("snapchat", "snap1chat"))

这种做法比较耗时间，循环次数的是最长字符串的长度


1.2中间分隔


第二种方法就比第一种快多了， 主要是将字符串平方后再对比，每次循环都可以减少 1/2长度

def no_equal(str1, str2):
    # 这里str2是最长的字符串，一最短的字符串 str1为对比基础
    nums = 1
    while len(str1) > 1:
        print("循环{}次".format(nums))
        nums += 1
        # 切割下标数
        end_nums = len(str1[0:]) // 2
        # print(end_nums)
        t_f = 0
        # 判断两个字符串前半部分的字符串是否相同
        if str1[0:end_nums] != str2[0:end_nums]:
            # 如果前半部分的字符串不相同，并且长的str1往后移一位和str2的后半部分也不相同的时候
            # 就说明这两个字符串有两处不相同，直接可以返回False了
            if str1[end_nums:] != str2[end_nums + 1:]:
                return False
            # 否则将相同的部分切除，得到不同的前半部分
            str1, str2 = str1[0:end_nums], str2[0:end_nums+1]
            t_f = 1
        if t_f == 0:
            # 切割对比出来的不相同的前半部分
            str1, str2 = str1[end_nums:], str2[end_nums:]
        # print(str1, str2)
        # 当切割到最后只剩一位字符的时候， 并且str1的最后一个字符和str2第一个或第二个字符相同的时候，可以返回False
        if len(str1) == 1 and (str1 == str2[0] or str1 == str2[-1]):
            return True

    return False


def equal(str1, str2):

    nums = 1
    while len(str1) > 1:
        lists = []
        print("循环{}次".format(nums))
        nums += 1
        # 获取字符串的中间的下标
        end_nums = len(str1) // 2
        t_f = 1
        # 如果两个字符串前半部分不相同，则添加到判断列表中
        if str1[0:end_nums] != str2[0:end_nums]:
            lists.append(str1[0:end_nums])
        # 如果两个字符串后半部分也不相同，也添加到判断列表中
        if str1[end_nums:] != str2[end_nums:]:
            lists.append(str1[end_nums:])
            t_f = 2
        #     如果判断列表中的数据大于1，这代表这两个字符串有最少两处不相同，直接可以结束循环了
        if len(lists) > 1:
            print(lists)
            return False
        # 通过上面两个if，判断两个字符串中是哪里（前半部分or后半部分）不相同，
        # 将相同的部分切除
        if t_f == 1:
            str1, str2 = str1[0:end_nums], str2[0:end_nums]
        else:
            str1, str2 = str1[end_nums:], str2[end_nums:]
    # 当两个字符串切割到最后一个时没有返回false时， 就不要再循环对比了，可以直接返回true了
    return True


def isStringAlike(str1, str2):
    # 如果两个单词字符数相等,调用equal 函数进行操作
    if len(str1) == len(str2):
        return equal(str1, str2)
    elif len(str1) + 1 == len(str2) or len(str1) - 1 == len(str2):
        # 如果两个字符串的长度差在1之间，调用no_equal 函数进行判断
        if len(str1) > len(str2):
            str1, str2 = str2, str1
        return no_equal(str1, str2)

    return False


# print(isStringAlike("snapchat", "sn11chat"))
print(isStringAlike("snapchat", "snapchat"))

直观的对比



可以看到，第二次的方法比第一次的要好很多