Deepak Saini - 2 years ago 168
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?

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.

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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download