Deepak Saini Deepak Saini - 6 months ago 37
Python Question

Compare strings, allowing one character difference

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?

Answer

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.

  1. your solution: 5.12
  2. Martijn Pieters' solution: 4.92
  3. enrico.bacis' and lakesh's solution: 5.51
  4. 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

Comments