比较字符串，允许一个字符的不同。

Question

我一直在尝试在Python中实现布尔表达式的制表方法。为此，我需要检查两个给定字符串是否仅在一个索引处不同。

例如，对于以下示例，该函数应返回以下结果：

• 0011和0111 - 真，因为两者仅在位置1处不同
• 0-001和0-101 - 真，因为只在2处不同
• 0-011和0-101 - 假，因为在2,3处不同

目前，我正在使用以下函数：

def match(s1,s2):

    l=[False,-1]##returns false when they cant be combined
    for i in range(len(s1)):
        if s1[:i]==s2[:i] and s1[i]!=s2[i] and s1[i+1:]==s2[i+1:]:
            l= [True,i]
            break
    return l

我希望以非常快的速度（低复杂度）实现它。在Python中有没有一种方法可以做到这一点？

- Deepak Saini

---

"0011" 是否等于 "011"？或者长度必须相同吗？ - user2864740

你是指“最多”吗？ - enrico.bacis

两个输入字符串具有相同的长度。 - Deepak Saini

我的意思是这两个字符串应该在恰好一个位置上不同。 - Deepak Saini

可能是Good Python modules for fuzzy string comparison?的重复问题。 - Back2Basics

Answer 1

我使用了Levenshtein距离来匹配只有一个字符添加或删除的不同字符串（而不是简单地替换）。因此：

• John's dog
• Johns dog

被视为匹配。

Levenshtein距离是将一个字符串替换为另一个字符串所需的编辑次数。上述两个字符串的Levenshtein距离为1，因为唯一需要做的就是删除一个字符。

要使用它，您可以简单地安装相应的Levenshtein Python模块：

pip install levenshtein

然后使用它：

from Levenshtein import distance 
def match(s1, s2):
    return distance(s1, s2) <= 1

- beledouxdenis

---

该软件包的自述文件中有一个警告，说明它已经更名为简单的levenshtein。代码仍然是相同的。 - Apollo-Roboto

Answer 2

这是一个更高效的解决方案，使用 Python 3 编写：

def match(s1, s2):
    ok = False

    for c1, c2 in zip(s1, s2):
        if c1 != c2:
            if ok:
                return False
            else:
                ok = True

    return ok

我没有检查长度差异，因为你说这两个字符串相等，但为了更一般的方法，我会添加它。

如果您需要不同字符的位置：

def match(s1, s2):
    pos = -1

    for i, (c1, c2) in enumerate(zip(s1, s2)):
        if c1 != c2:
            if pos != -1:
                return -1
            else:
                pos = i

    return pos

以下是使用timeit测试match("0-001", "0-101")的基准测试结果。我将所有解决方案转换为py3并删除了长度测试。

1. 你的解决方案：5.12
2. Martijn Pieters的解决方案：4.92
3. enrico.bacis和lakesh的解决方案：5.51
4. 我的解决方案：2.42

使用更长的字符串进行测试：

Martijn Pieters的解决方案：

timeit.timeit('match("0-0016ub5j2oi06u30tj30g6790v3nug[hoyj39867i6gy9thvb05y4b896y3n098vty98thn98qg5y4n8ygnqp", "0-0016ub5j2oi06u30tj30g6790v3gug[hoyj39867i6gy9thvb05y4b896y3n098vty98thn98qg5y4n8ygnqp")', setup="""
def match(s1, s2):
    combo = zip(s1, s2)
    return any(c1 != c2 for c1, c2 in combo) and all(c1 == c2 for c1, c2 in combo)
""")

结果: 32.82

我的解决方案:

timeit.timeit('match("0-0016ub5j2oi06u30tj30g6790v3nug[hoyj39867i6gy9thvb05y4b896y3n098vty98thn98qg5y4n8ygnqp", "0-0016ub5j2oi06u30tj30g6790v3gug[hoyj39867i6gy9thvb05y4b896y3n098vty98thn98qg5y4n8ygnqp")', setup="""
def match(s1, s2):
    ok = False

    for c1, c2 in zip(s1, s2):
        if c1 != c2:
            if ok:
                return False
            else:
                ok = True

    return ok
""")

结果：20.21

- Marco Sulla

---

你可以在那个点上直接返回False，而不是将“ok”设置为False并跳出循环。 - Martijn Pieters

你能否更新一下，包括所有的测试输入，并且加入更长的字符串测试吗？ - Martijn Pieters

@lucas 这是一种非常高效的方法。你能否修改你的函数，使其还能返回差异的位置（索引）呢？非常感谢。 - Deepak Saini

@DeepakSaini：你可以这样做：pos=-1; for i, cc in enumerate(zip(s1, s2)): if cc[0] != cc[1]: if pos != -1: return -1; else: pos =i 然后 return pos。如果你只需要位置，就不需要返回 True 或 False，因为 -1 表示没有匹配。 - Marco Sulla

@lucas 非常感谢。我一直被这个问题困扰了一段时间。 - Deepak Saini

Answer 3

在Python 2中，使用future_builtins.zip()（Python 2和3兼容的zip()-作为迭代器）（在Python 3中内置函数可以很好地完成）按字符组合两个字符串，然后使用any()和all()遍历生成的迭代器：

try:
    from future_builtins import zip
except ImportError:
    pass

def match(s1, s2):
    if len(s1) != len(s2):
        return False
    combo = zip(s1, s2)
    return any(c1 != c2 for c1, c2 in combo) and all(c1 == c2 for c1, c2 in combo)

这是因为combo是一个迭代器；它按需一次产生一对字符，并且any()和all()只需要取用足够数量的对来确定它们的结果。

any()会在找到两个不相等的字符时立即停止迭代。只有当所有剩余的字符都相等时，all()才会返回True。

因此，只有当存在恰好一对不同的字符时，上述两个条件才为真。

由于使用了迭代器方法，因此上述方法仅执行最少量的工作来确定字符串是否匹配；一旦发现第二对不匹配的字符，迭代就停止了；查看其余字符组合没有意义。

演示（Python 2，因此导入zip()）：

>>> from future_builtins import zip
>>> def match(s1, s2):
...     if len(s1) != len(s2):
...         return False
...     combo = zip(s1, s2)
...     return any(c1 != c2 for c1, c2 in combo) and all(c1 == c2 for c1, c2 in combo)
... 
>>> match('0011', '0111')
True
>>> match('0-001', '0-101')
True
>>> match('0-011', '0-101')
False

- Martijn Pieters

---

@ Matrtijn Pieters 谢谢。但是我遇到了错误，“future_builtins”模块不存在。 - Deepak Saini

@DeepakSaini：没错，那么zip()已经是“未来内置函数”了；在这种情况下，调整以忽略导入错误。 - Martijn Pieters

非常酷的使用zip作为迭代器。然而，如果字符串相等，它看起来会返回false--任何表达式都将返回false，因此整个逻辑表达式也将返回false。 - Dunes

@Dunes：问题中没有说明如果两个字符串完全相同应该返回 True。 - Martijn Pieters

这是我对标题“allowing one”的理解，即允许最多一个。但问题的其余部分支持你的解释。我意识到将 any(...) and all(...) 转换为 any(...) or all(...) 将回答我的问题解释。 - Dunes

Answer 4

def match(a,b):
    s = sum([a[i] != b[i] for i in range(len(a))])
    if s == 1:
       return True
    else:
       return False

- lakshmen

---

或者你可以写成 return s<2。 - spicavigo

Answer 5

同样的长度

如果这两个字符串具有相同的长度：

def match(s1, s2):
    return sum(s1[i] != s2[i] for i in xrange(len(s1))) <= 1

你可以像这样创建一个匹配器生成器：

def create_matcher(maxdiff):
    return lambda s1, s2: sum(s1[i] != s2[i] for i in xrange(len(s1))) <= maxdiff

match = create_matcher(1)

例子：

print match('0011', '0111')      # True
print match('0-001', '0-101')    # True
print match('0-011', '0-101')    # False

---

长度不同

如果它们的长度不同，我们可以假设超出的字符是不同的，因此：

def match(s1, s2):
    l = min(len(s1), len(s2))
    return sum(s1[i] != s2[i] for i in xrange(l)) + abs(len(s1) - len(s2)) <= 1

- enrico.bacis