#!/usr/bin/env python
def letter_num(letter):
num = ord(letter)
if num < 91:
return num - 65
else:
return num - 97 + 26
class Node:
def __init__(self, letter=""):
self.letter = letter[0]
self.next = [None for i in range(0,52)]
self.leaf = True
self.word = False
def insert(self, letter=""):
if len(letter) == 0:
return
num = letter_num(letter[0])
n = self.next[num]
if n == None:
self.next[num] = Node(letter[0])
self.leaf = False
n = self.next[num]
if len(letter) == 1:
self.word = True
return
n.insert(letter[1:])
def match(self, letter):
if letter[0] == self.letter:
if len(letter) == 1 :
if self.word:
return True
else:
return False
if self.next[letter_num(letter[1])] != None:
return self.next[letter_num(letter[1])].match(letter[1:])
return False
if __name__ == "__main__":
word_dict = []
final_dict = []
# Initial the word_dict
word_dict = word_dict + [Node(chr(c)) for c in range(65, 91)]
word_dict = word_dict + [Node(chr(c)) for c in range(97, 123)]
# Build the word_dict according to /usr/share/dict/words
with open("/usr/share/dict/words") as f:
for word in f:
word_dict[letter_num(word[0])].insert(word[1:].strip())
# Processing the word
word = "planet"
avail_word = [word]
while len(avail_word[0]) > 0:
cur_word = avail_word.pop()
if word_dict[letter_num(cur_word[0])].match(cur_word):
final_dict.append(cur_word)
avail_word = [
cur_word[:i] + cur_word[i+1:] for i in range(0, len(cur_word))]
print final_dict