比较字符串,允许一个字符差异

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中这样做？

Answer 1

我使用Levenshtein距离匹配不同的字符串,只添加或删除一个字符(而不是简单地替换).所以:

• 约翰的狗
• 约翰斯狗

被视为匹配.

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

要使用它,您只需安装相应的Levenshtein python模块:

pip install python-Levenshtein

然后使用它:

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

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