使用 set() 解决“一去不复返”

Question

我正在参加 Udemy 课程。我正在处理的问题是取两个字符串并确定它们是否彼此“一次编辑”。这意味着您可以对一个字符串进行一次更改——更改一个字母、添加一个字母、删除一个字母——并使其与另一个相同。

例子：

s1a = "abcde"
s1b = "abfde"

s2a = "abcde"
s2b = "abde"

s3a = "xyz"
s3b = "xyaz"

• s1a将 更改'c'为'f'。
• s2a删除'c'.
• s3a添加'a'.

教师解决方案（和测试套件）：

def is_one_away(s1, s2):
    if len(s1) - len(s2) >= 2 or len(s2) - len(s1) >= 2:
        return False
    elif len(s1) == len(s2):
        return is_one_away_same_length(s1, s2)
    elif len(s1) > len(s2):
        return is_one_away_diff_lengths(s1, s2)
    else:
        return is_one_away_diff_lengths(s2, s1)


def is_one_away_same_length(s1, s2):
    count_diff = 0
    for i in range(len(s1)):
        if not s1[i] == s2[i]:
            count_diff += 1
            if count_diff > 1:
                return False
    return True


# Assumption: len(s1) == len(s2) + 1
def is_one_away_diff_lengths(s1, s2):
    i = 0
    count_diff = 0
    while i < len(s2):
        if s1[i + count_diff] == s2[i]:
            i += 1
        else:
            count_diff += 1
            if count_diff > 1:
                return False
    return True


# NOTE: The following input values will be used for testing your solution.
print(is_one_away("abcde", "abcd"))  # should return True
print(is_one_away("abde", "abcde"))  # should return True
print(is_one_away("a", "a"))  # should return True
print(is_one_away("abcdef", "abqdef"))  # should return True
print(is_one_away("abcdef", "abccef"))  # should return True
print(is_one_away("abcdef", "abcde"))  # should return True
print(is_one_away("aaa", "abc"))  # should return False
print(is_one_away("abcde", "abc"))  # should return False
print(is_one_away("abc", "abcde"))  # should return False
print(is_one_away("abc", "bcc"))  # should return False

当我看到这个问题时，我决定使用set().

我发现这很有用： 在 python 中与 set.intersection 相对？

这是我尝试的解决方案：

def is_one_away(s1, s2):
    if len(set(s1).symmetric_difference(s2)) <= 1:
        return True

    if len(set(s1).symmetric_difference(s2)) == 2:
        if len(set(s1).difference(s2)) == len(set(s2).difference(s1)):
            return True
        return False
    return False

当我在线运行我的解决方案时（您可以在课程本身中进行测试）我在最后一个测试套件项目上失败了：

False != True : 
Input 1: abc
Input 2: bcc
Expected Result: False
Actual Result: True

我试了又试，但我无法让最后一个测试项目起作用（至少在不破坏一堆其他东西的情况下不能）。

不能保证我可以使用set()基于解决方案的解决方案来解决完整的测试套件，但是由于我是一个项目，我真的很想看看我是否可以完成它。

Answer 1

这无法通过此测试，因为您只查看唯一字符：

>>> s1 = 'abc'
>>> s2 = 'bcc'
>>> set(s1).symmetric_difference(s2)
{'a'}

那是一组长度为1，但有两个字符改变了。通过转换为集合，您只会看到输入中至少有一个'c'字符s2，而不是现在有两个。

您的方法失败的另一种方式是，如果字符的顺序发生变化。'abc'距离 有两个变化'cba'，但您的方法也无法检测到这些变化。

你不能用集合解决这个问题，因为集合删除了两个重要的信息：一个字符出现的次数，以及字符的排列顺序。