Skip to content

Instantly share code, notes, and snippets.

@steder
Created January 21, 2012 21:05
Show Gist options
  • Save steder/1653998 to your computer and use it in GitHub Desktop.
Save steder/1653998 to your computer and use it in GitHub Desktop.
Words Blog Post Snippets
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")
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")
"""
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment