CMU Coding Bootcamp
thecoded.prof
1def spellCheck(lookupWord: str, words: str) -> str | None:
2 """Spell check a word against a list of words."""
3 map = {}
4 for word in words.split():
5 map[word] = levenshtein(lookupWord, word)
6 min_distance = min(map.values())
7 if min_distance >= 3:
8 return None
9 return ",".join([word for word in map.keys() if map[word] == min_distance])
10
11
12# from: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python
13def levenshtein(s1: str, s2: str) -> int:
14 if len(s1) < len(s2):
15 return levenshtein(s2, s1)
16
17 # len(s1) >= len(s2)
18 if len(s2) == 0:
19 return len(s1)
20
21 previous_row = range(len(s2) + 1)
22 for i, c1 in enumerate(s1):
23 current_row = [i + 1]
24 for j, c2 in enumerate(s2):
25 insertions = (
26 previous_row[j + 1] + 1
27 ) # j+1 instead of j since previous_row and current_row are one character longer
28 deletions = current_row[j] + 1 # than s2
29 substitutions = previous_row[j] + (c1 != c2)
30 current_row.append(min(insertions, deletions, substitutions))
31 previous_row = current_row
32
33 return previous_row[-1]
34
35
36print("Testing spellCheck()...", end="")
37words = "cat cow dog frog"
38assert spellCheck("frog", words) == "frog" # frog is correct
39assert spellCheck("cats", words) == "cat" # cat is distance 1
40assert spellCheck("caw", words) == "cat,cow" # cat and cow are distance 1
41assert spellCheck("drog", words) == "dog,frog" # dog and frog are distance 1
42assert spellCheck("kit", words) == "cat" # cat is distance 2
43assert spellCheck("ack", words) == None # cat, cow, and dog are
44# distance 3 (too far)
45print("Passed!")