public
Created

Words Blog Post Snippets

  • Download Gist
sorted.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
import itertools
 
class Dictionary(object):
def __init__(self):
self.words = {}
 
def insert(self, word):
letters = "".join(sorted(word))
if letters not in self.words:
self.words[letters] = [word]
elif word not in self.words[letters]:
self.words[letters].append(word)
 
def getAnagrams(self, word):
letters = "".join(sorted(word))
words = self.words.get(letters, [])
return words
 
def getScrabbleWords(self, letters):
words = []
letters = "".join(sorted(letters))
for n in xrange(2, len(letters)+1):
for combination in itertools.combinations(letters, n):
candidate = "".join(combination)
w = self.words.get(candidate, [])
if w:
words.extend(w)
 
words = list(set(words))
words.sort()
return words
 
d = Dictionary()
with open("words.txt") as f:
for word in f:
d.insert(word)
 
d.getAnagrams("ehllo")
d.getScrabbleWords("ehllo")
trie.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
class Trie(object):
def __init__(self):
self.trie = {}
 
def insert(self, word):
trieNode = trie
for letter in word:
if not letter in trieNode:
trieNode[letter] = {}
trieNode = trieNode[letter]
trieNode[EOW] = 1
 
def depthFirstWords(self, letters, trieNode, accumulator):
for letter, node in trieNode.iteritems():
if letter != EOW and node:
if node.get(EOW, False):
accumulator.append("".join(letters + letter))
self.depthFirstWords(letters+letter, node, accumulator)
return accumulator
 
def getWordsFromTrieWithTransform(self, trie, letters, transform):
trieNode = trie
letters = transform(letters)
for letter in letters:
trieNode = trieNode.get(letter, None)
if not trieNode:
return None
 
words = []
if trieNode.get(EOW, False):
words.append("".join(letters))
 
self.depthFirstWords(letters, trieNode, words)
 
words = [transform(word) for word in words]
words.sort()
return words
 
def getWordsStartingWith(self, letters):
identity = lambda x: x
return self.getWordsFromTrieWithTransform(self.trie, letters, identity)
 
trie = Trie()
with open("words.txt") as f:
for word in f:
trie.insert(word)
 
trie.getWordsStartingWith("hello")
words_simple.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
"""
This works but is considerably slower because it has to check
every permutation of the letters.
"""
 
import itertools
import sys
 
dictionary = {}
 
def getScrabbleWords(letters):
letters = letters.strip().lower()
words = []
for x in xrange(2, len(letters)+1):
for permutation in itertools.permutations(letters, x):
word = "".join(permutation)
if word in dictionary:
words.append(word)
words.sort()
return words
 
with open("words.txt") as f:
for word in f:
dictionary[word.strip().lower()] = 1
print getScrabbleWords("ehllo")

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.