I got inspired by this C# question. It asks to write a program to output all possible words (included in a dictionary) which fit a string of letters obtained by swiping the finger over the keyboard, as is often done with mobile keyboards.
Description
Software like Swype and SwiftKey lets smartphone users enter text by dragging their finger over the on-screen keyboard, rather than tapping on each letter.
You'll be given a string of characters representing the letters the user has dragged their finger over.
For example, if the user wants "rest", the string of input characters might be "resdft" or "resert". Input
Given the following input strings, find all possible output words 5 characters or longer.
qwertyuytresdftyuioknn gijakjthoijerjidsdfnokg
Output
Your program should find all possible words (5+ characters) that can be derived from the strings supplied.
Use http://norvig.com/ngrams/enable1.txt as your search dictionary.
The order of the output words doesn't matter.
queen question gaeing garring gathering gating geeing gieing going goring
Notes/Hints
Assumptions about the input strings:
- QWERTY keyboard
- Lowercase a-z only, no whitespace or punctuation
- The first and last characters of the input string will always match the first and last characters of the desired output word
- Don't assume users take the most efficient path between letters
- Every letter of the output word will appear in the input string
The function read_vocabulary
reads the file and saves the words in a nested dictionary structure, where the first key is the first letter of the word and the second key the last letter of the word (this improves running time by about a factor 2 with respect to a simple set
).
I saved the linked word list as dictionary.txt on my computer.
The find_words
function tries to find all characters of a word (with the right first and last letter) in the pattern
string and yields
it if it found all.
The call to sorted
in the last part is not necessary from the defined interface (any ordering is fine), but I like it better this way.
All comments are welcome, especially about improving readability of the code.
import string
from collections import defaultdict
def read_vocabulary(file_name):
vocabulary = {letter: defaultdict(set) for letter in string.lowercase}
with open(file_name) as dict_file:
for word in dict_file:
word = word.strip().lower()
vocabulary[word[0]][word[-1]].add(word)
return vocabulary
def find_words(vocabulary, pattern, length=5):
"""
Search `vocabulary` for words matching `pattern` generated by
swiping the finger over the keyboard.
Yields all matching words
>>> vocabulary = {'q': {'n': {'queen'}, 'r': {'qualor'}}}
>>> list(find_words(vocabulary, 'qwertyuytresdftyuioknn'))
['queen']
"""
for word in vocabulary[pattern[0]][pattern[-1]]:
if len(word) >= length:
i = 1
for character in word[1:-1]:
try:
i = pattern.index(character, i)
except ValueError:
break
else:
yield word
if __name__ == "__main__":
words = ["qwertyuytresdftyuioknn",
"gijakjthoijerjidsdfnokg",
"cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews"]
vocabulary = read_vocabulary("dictionary.txt")
for word in words:
# print word
print " ".join(sorted(find_words(vocabulary, word), key=len, reverse=True))
Regarding run-time:
With the 1 million random characters, as linked at the other question, this code runs in about 0.14 seconds (as determined by python -m cProfile script.py
), which includes reading the 1M characters from a file (because they are too big to just paste them in...).
else
clause in the for statement, this might be my bad... \$\endgroup\$line_profiler
to see if what is the bottleneck in your code. \$\endgroup\$