Compare strings, allowing one character difference

Question

I have been trying to implement tabular method for simplification of boolean expressions in python. For that I need to check whether two given strings differ at only one index
for example, the function should return the following for the following examples:

0011
and
0111
- true as the two differ only at position 1

0-001
and
0-101
- true as differ at only 2

0-011
and
0-101
- false as differ at 2,3

right now I am using the following function:

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

I want to implement it in a very fast manner (low complexity). Is there a way to do so in python?

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

This is a more well-performing solution, coded in 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

I do not checked for length difference because you said the two strings are equal, but for a more general approach I would add it.

If you need the position of the different character:

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

These are benchmarks performed with timeit, tested with match("0-001", "0-101"). I translated all solutions to py3 and removed length test.

your solution: 5.12
Martijn Pieters' solution: 4.92
enrico.bacis' and lakesh's solution: 5.51
my solution: 2.42

Tests with a longer string:

Martijn Pieters' solution:

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)
""")

result: 32.82

My solution:

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
""")

Result: 20.21

Compare strings, allowing one character difference

Sign up