valoris
BAN USERHow about a prefix tree?
We can convert a list of words into a prefix tree: each node we'll be a sorted list of letters, and have reference to one or more indexes of a corresponding words:
def build_prefix_tree(words):
tree = PrefixTree()
for i, word in enumerate(words):
tree.insert(value=sorted(word), index=i)
return tree
So each tree node can have multiple indexes:
Prefix tree with "node (indexes)":
acc (4)
/
ac (2) - act (0, 1)
\
psto (4)
In the tree above each word is sorted alphabetically and has index or indexes of the original word position in a `words` array.
Now, we can find all the matches in the prefix tree:
def scribble(chars, words):
chars = ''.join(sorted(chars))
prefix_tree = build_prefix_tree(words)
results
nodes = prefix_tree.root_nodes
while nodes:
node = nodes.pop()
if node == chars[:len(node)]:
results.extend(words[i] for i in node.indexes)
nodes.extend(node.children)
return sorted(results) # For consistent results.
Another solution in Python with O(N1 * N2 * ... * Nk), where Nk is a number of elements in list number k.
def combine(input_list, words=None):
if words is None:
words = []
if input_list is None:
print ' '.join(words)
return
for word in input_list[0]:
combine(input_list[1:] if len(input_list) > 1 else None, words + [word])
combine([('quick', 'slow'), ('brown', 'red'), ('fox', 'dog')])
DP solution, any comments? Works for given numbers, including 12.
def squares(n):
results = [0] * (n + 1)
squares = []
for i in range(1, n + 1):
if i ** 2 <= n:
squares.append(i)
count = i
for j in [r for r in squares if r ** 2 <= count]:
if results[i - j ** 2] + 1 < count:
count = results[i - j ** 2] + 1
results[i] = count
return results[n]
Solution in Python in linear O(k):
def find_kth_node(tree, k):
return _kth_node_recursive(tree.root_node, k)[1]
def _kth_node_recursive(node, k):
kth_node = None
if node.left_child:
k, kth_node = _kth_node_recursive(node.left_child, k)
if kth_node:
return k, kth_node
k -= 1
if k == 0:
return k, node
if node.right_child:
k, kth_node = _kth_node_recursive(node.right_child, k)
return k, kth_node
I was thinking about implementing this as a binary tree. Something along this lines in Pythonish pseudocode:
MAX_QAZ = 0
class Node:
global MAX_QAZ
def __init__(self, value):
self.qaz = 0
self.value = value
self.right_child, self.left_child = None, None
def insert(self, number):
if number > self.value:
if self.right_child is not None:
self.right_child.insert(number)
else:
self.right_child = Node(number)
self.qaz += 1
if self.qaz > MAX_QAZ:
MAX_QAZ = self.qaz
self.left_child.increment_childrens_qaz()
else:
if self.left_child is not None:
self.left_child.insert(number)
else:
self.left_child = Node(number)
def increment_childrens_qaz(self):
self.qaz += 1
if self.qaz > MAX_QAZ:
MAX_QAZ = self.qaz
self.left_child.increment_childrens_qaz()
self.right_child.increment_childrens_qaz()
class BinaryTree:
def insert(self, number):
if self.root_node is None:
self.root_node = Node(number)
return
self.root_node.insert(number)
tree = BinaryTree()
for number in list:
tree.insert(number)
print MAX_QUAZ
Basically each time a node is inserted it's qaz is initialized to 0. If it's inserted to the left of existing node - existing node's qaz doesn't change. If it is inserted on the right of the existing node - existing node's qaz increments, and so does qaz of everything to the left of the existing node.
- valoris January 27, 2015
Python:
- valoris February 19, 2015