cost-of-data-11

Strings can be efficiently stored as a data structure, to have efficient searching methods.
A new startup is going to use this method, but they don't have much space. So they want to check beforehand how much memory will be required for their data. 
Following method describes the way in which this startup's engineers save the data in the structure.

Suppose they have 5 strings/words: et,eq,bd,be,bdp
A empty node is kept NULL, and strings are inserted into the structure one by one. 
Initially the structure is this:

NULL

After inserting "et", the structure is this:

NULL
 |
 e
 |
 t

After inserting "eq", the structure is this:

   NULL
   /
  e
 / \
t   q

After inserting "bd", the structure is this:

   NULL
   /  \
  e    b
 / \    \
t   q    d

After inserting "be", the structure is this:

     NULL
   /     \
  e       b
 / \     / \
t   q   e   d

After inserting "bdp", the structure is this:

    NULL
   /     \
  e       b
 / \     / \
t   q   e   d
             \
              p

Therefore a total of 8 nodes are used here.    

Input: 
First line contains N, the number of strings they have.  
Each of the next N lines contain one string. Each string consists only of lowercase letters.    

Output: 
Print the required number of nodes.    

**Constraints: 
1 ≤ N ≤ 10^5     
Length of each string  ≤ 30    

Note: No two strings are same, though one string could be prefix of another.

SAMPLE INPUT
5
et
eq
bd
be
bdp

SAMPLE OUTPUT
8

Source: hackerearth | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures


Solutions:
import sys
inp = []
try:
	while True:
		inp.append(input())
except:
	pass
	
test = inp[1:]
N = int(inp[0])
if N > 10**5:
	sys.exit(1)

#test = ["et", "eq", "bd", "be", "bdp"]

class Node:
	def __init__(self, func):
		self.increment = func		
		self.children = {}
	def add(self, ch):
		try:
			n = self.children[ch]
		except:
			n = Node(self.increment)
			n.letter = ch
			self.increment()
			self.children[ch] = n			
		return n
		
class store:
	def __init__(self):
		self.cost = 0;
		self.root = Node(self.inc)
		self.root.leter = '\0'
	def add(self, text):
		cur = self.root
		for x in text:
			try:
				cur = cur.children[x]
			except:
				cur = cur.add(x)
	def GetCost(self):
		return self.cost + 1
	
	def inc(self):
		self.cost = self.cost + 1
st = store()	
for s in test:
	if len(s) > 30:
		sys.exit(2)
	st.add(s)

print(st.GetCost())


import fileinput

class Node(object):
	def __init__(self,data):
		self.data=data
		self.children={} # {'data' => Node}
		self.max_score =0
		
	def add_child(self,data,score):
		if data in self.children:
			pass
		else:
			self.children[data]=Node(data)
		self.children[data].max_score= score
		return self.children[data]
	
	def is_leaf(self):
		return len(self.children) == 0 and self.data != ""
	
	def __str__(self, *args, **kwargs):
		return self.data
	
class Trie(object):
	def __init__(self):
		self.root= Node("")
		self.num_node=1
		
	def add_string(self,string, score):
		node, end_index = self.find_path(string,-1)
		length= len(string)
		
		for i in range(end_index,length):
			if node.max_score < score:
				node.max_score = score
			node= node.add_child(string[i], score)
			self.num_node=self.num_node + 1
	
	# return node
	def find_path(self, string, score):
		node= self.root
		i= 0
		for c in string:
			if c in node.children:
				i=i+1
				node=node.children[c]              
			else:
				break
		return node, i
	
	def max(self,node):
		pass
		
if __name__=="__main__":
	f= fileinput.input()
	n= int(f.readline())
	
	trie= Trie()
	
	while n > 0:
		n=n-1
		line = f.readline().strip()
		trie.add_string(line, -1)
	print(trie.num_node)
	


import sys
inp = []
try:
	while True:
		inp.append(input())
except:
	pass
	
test = inp[1:]
N = int(inp[0])
if N > 10**5:
	sys.exit(1)

#test = ["et", "eq", "bd", "be", "bdp"]

class Node:
	def __init__(self, func):
		self.increment = func		
		self.children = {}
	def add(self, ch):
		try:
			n = self.children[ch]
		except:
			n = Node(self.increment)
			n.letter = ch
			self.increment()
			self.children[ch] = n			
		return n
		
class store:
	def __init__(self):
		self.cost = 0;
		self.root = Node(self.inc)
		self.root.leter = '\0'
	def add(self, text):
		cur = self.root
		for x in text:
			try:
				cur = cur.children[x]
			except:
				cur = cur.add(x)
	def GetCost(self):
		return self.cost + 1
	
	def inc(self):
		self.cost = self.cost + 1
st = store()	
for s in test:
	if len(s) > 30:
		sys.exit(2)
	st.add(s)

print(st.GetCost())


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
class Node():
	def __init__(self,alphabet):
		self.value = alphabet
		self.children = []

class Trie():
	def __init__(self):
		self.root = Node("root")

	def insertWord(self,word):
		letters = list(word)
		currentNode = self.root
		while True:
			try:
				letter = letters.pop(0)
			except IndexError:break
			found = 0
			for node in currentNode.children:
				if node.value == letter:
					currentNode = node
					found = 1
					break
			if found == 1: continue
			newNode = Node(letter)
			currentNode.children.append(newNode)
			currentNode = newNode
				
	def numOfNodes(self):
		self.totalNodes = 0
		def calc(currNode):
			self.totalNodes = self.totalNodes + len(currNode.children) 
			for node in currNode.children:
				calc(node)
		calc(self.root)
		return self.totalNodes+1

N = int(input())
trie = Trie()
for x in range(N):
	word = input()
	trie.insertWord(word)
print(trie.numOfNodes())