1

Here is the question:

Given two words with the same number of letters in each, work out how many letters need to be changed to get from the first word to the second. A more complex version of edit distance is commonly used in spelling auto-correct algorithms on phones and word processors to find candidate corrections.

The two words should be read from the user with one word per line. For example:

Word 1: hello
Word 2: jelly
2

this is all I got: 

w1 = input('Word 1: ')
w2 = input('Word 2: ')
for i in w1:
  for o in w2:
    print(i, o)

How do I do this?

Improve this question

4 Answers 4

Reset to default
6

You can try something like:

sum(c1 != c2 for c1,c2 in zip(w1,w2))

zip(w1,w2) creates a generator that returns tuples consisting of corresponding letters of w1 and w2. i.e.:

>>> list(zip(w1,w2))
[('h', 'j'), ('e', 'e'), ('l', 'l'), ('l', 'l'), ('o', 'y')]

We iterate over these tuples (c1 gets assigned to each first char and c2 to each second char) and check if c1 != c2. We add up all the instances for which this condition is satisfied to arrive at out answer.

(See zip() and sum())

>>> w1 = 'hello'
>>> w2 = 'jelly'
>>> 
>>> sum(c1 != c2 for c1,c2 in zip(w1,w2))
2
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

thank you! It worked! Can you please explain what is happening in the code?
@Samir Sure, I added some explanation.
3

Using difflib:

>>> import difflib
>>> w1, w2 = 'hello', 'jelly'
>>> matcher = difflib.SequenceMatcher(None, w1, w2)
>>> m = sum(size for start, end, size in matcher.get_matching_blocks())
>>> n = max(map(len, (w1, w2))) # n = len(w1)
>>> n - m
2
Improve this answer

1 Comment

difflib is generally a good place to look when solving these types of problems. But for something this simple, it seems like overkill.
2

A functional approach:

>>> from itertools import starmap
>>> from operator import ne
>>> sum(starmap(ne, zip(word1, word2)))
2
Improve this answer

3 Comments

The no import and not using zip approach:: sum(map(str.__ne__, a, b))
@JonClements: Nice! Note that there's a subtle difference, as zip() stops after the shortest word, while map() goes on until the longest word is exhausted, using None as a fill value, in case the words have different lengths.
True, but I would consider that more desired behaviour as str.__ne__ will end up with a TypeError which is also in effect an assertion that the lengths are equal as stated in the problem text.
1

If the words are always going to be the same length you can use zip to loop through both lists at once:

w1 = input('Word 1: ')
w2 = input('Word 2: ')
changes=0    
    for i, o in zip(w1, w2):
    if i != o:
        changes+=1

print "Changes needed: "+str(changes)
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.