Something went wrong. Try again.
CMU Coding Bootcamp
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546def spellCheck(lookupWord: str, words: str) -> str | None: """Spell check a word against a list of words.""" map = {} for word in words.split(): map[word] = levenshtein(lookupWord, word) min_distance = min(map.values()) if min_distance >= 3: return None return ",".join([word for word in map.keys() if map[word] == min_distance])
# from: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Pythondef levenshtein(s1: str, s2: str) -> int: if len(s1) < len(s2): return levenshtein(s2, s1)
# len(s1) >= len(s2) if len(s2) == 0: return len(s1)
previous_row = range(len(s2) + 1) for i, c1 in enumerate(s1): current_row = [i + 1] for j, c2 in enumerate(s2): insertions = ( previous_row[j + 1] + 1 ) # j+1 instead of j since previous_row and current_row are one character longer deletions = current_row[j] + 1 # than s2 substitutions = previous_row[j] + (c1 != c2) current_row.append(min(insertions, deletions, substitutions)) previous_row = current_row
return previous_row[-1]
print("Testing spellCheck()...", end="")words = "cat cow dog frog"assert spellCheck("frog", words) == "frog" # frog is correctassert spellCheck("cats", words) == "cat" # cat is distance 1assert spellCheck("caw", words) == "cat,cow" # cat and cow are distance 1assert spellCheck("drog", words) == "dog,frog" # dog and frog are distance 1assert spellCheck("kit", words) == "cat" # cat is distance 2assert spellCheck("ack", words) == None # cat, cow, and dog are# distance 3 (too far)print("Passed!")