Instantly share code, notes, and snippets.

steder/sorted.py Created Jan 21, 2012

What would you like to do?
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")