2
\$\begingroup\$

Input
The first line of input contains a string s: the word misspelled by your partner. Assume that your partner did not add or remove any letters; they only replaced letters with incorrect ones. The next line contains a single positive integer n indicating the number of possible valid words that your partner could have meant to write. Each of the next n lines contains each of these words. There is guaranteed to be at least one word of the same length as the misspelled word.

Output
Output a single word w: the word in the dictionary of possible words closest to the misspelled word. "Closeness" is defined as the minimum number of different characters. If there is a tie, choose the word that comes first in the given dictionary of words.

Example:

input
deat
6
fate
feet
beat
meat
deer
dean

output
beat
s = input()
n = int(input())
count_list = []
word_list = []
final = []

count = 0

for i in range(n):
    N = input()
    
    
    for j in range(len(N)):
        if s[j] == N[j]:
            count += 1
            
    count_list.append(count)
    word_list.append(N)
    count = 0

max_c = count_list[0]
for i in range(len(count_list)):
    if count_list[i] > max_c:
        max_c = count_list[i]

indices = [index for index, val in enumerate(count_list) if val == max_c]
      
for i in range(len(indices)):
    final.append(word_list[indices[i]])

print(final[0])

This is what I managed to write. This code passed 3 test cases but failed the 4th. I tried to do final.sort() to put them in alphabetical order, but it fails on the 2nd test case (I can only see the 1st test case which is included in this post). What can I do to fix this? The code only allows words with the same number of characters as the control string, which might be causing the wrong test case since one of the test cases might have more or less characters than the control string? Can someone help?

\$\endgroup\$
2

1 Answer 1

3
\$\begingroup\$

Code Review

Your code doesn't pass all of the test cases, so by some definitions, it is not ready for a code review. However, it is close enough to working and has several code-habits that should be corrected, that I'll give you a Code Review anyway.

Variable names

Both count_list and word_list are nice, descriptive variable names. final is ok, but not very descriptive (final what?). However, variable names like s, n, N are terrible, especially in global scope. The fact the n is a count, and N is a string is outright confusing.

PEP 8: The Style Guide for Python Code recommends all variable names should be in snake_case. Uppercase letters are used only in NAMED_CONSTANTS and ClassNames.

Variable Types

count_list and word_list are parallel data structures. count_list[j] is the count of matching letters in word_list[j].

The would be better expressed as a dictionary. Ie) match_length = {} and match_length[word] = count. As of Python 3.6 (December 2016), dictionaries are ordered by insertion order, so determining which word came before other words is still possible.

Throw-away variables

In the first loop, for i in range(n):, the variable i is never used. PEP-8 recommends using _ for these kind of variables. Ie) for _ in range(n):

Initialize before use

You have:

count = 0

for i in range(n):
    ...
    
    for j in range(len(N)):
        if s[j] == N[j]:
            count += 1     
    ...
    count = 0

The variable count is set to zero in two different statements. The first initialization is before the outer loop, so it looks like it might be counting items found in the outer loop, but it is not; it is counting in the inner loop. This should be reorganized:


for i in range(n):
    ...
    count = 0
    
    for j in range(len(N)):
        if s[j] == N[j]:
            count += 1     
    ...

Now you only have one location where count is reset to zero. The code should be easier to understand.

Loop over values, not indices

The inner loop iterates over the indices of N, assigning successive values to j, but the contents of the loop only ever uses j as an index: s[j] and N[j]. Python is optimized for iterating over the values in containers.


    count = 0
    for s_letter, candidate_word_letter in zip(s, N):
        if s_letter == candidate_word_letter:
            count += 1

Built in functions

max_c = count_list[0]
for i in range(len(count_list)):
    if count_list[i] > max_c:
        max_c = count_list[i]

This is reinventing the wheel. It is such a common operation, Python has a built-in function for doing it.

max_c = max(count_list)

Incorrect Output

This code passed 3 test cases but failed the 4th

Relook at your problem description. Print it out. Using a pen, cross off all the conditions that you test for. At the end, you should see something which you haven't tested. Adding a check for that will solve your problem.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'm going to leave the question open because this is a good answer. \$\endgroup\$
    – pacmaninbw
    Oct 17, 2021 at 12:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.