# A/C Python solution, though only beat 1.5%, very straightforward to understand, build a tree, then traverse the tree node

• class Node(object):
def init(self, data):
self.data = data
self.children = []

``````def add_child(self, obj):
self.children.append(obj)
``````

class Solution(object):

``````def generateAbbreviations(self, word):
"""
:type word: str
:rtype: List[str]
"""
lenWord = len(word)
#print "lenWord = ", lenWord
# result = []
# elements

# tmp = sorted(["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"])
# print "tmp = ", tmp

# res = [word for i in range(2**lenWord)]
# print "res = ", res

nodeRoot = Node("")
curNode = nodeRoot
result = []

def build_tree(curNode, remainingWord):
#print "remainingWord = ", remainingWord

lenRemainingword = len(remainingWord)
if lenRemainingword == 0:
#print "no more remaining"
return

else:
c = remainingWord[0:1]
remainingWord = remainingWord[1:]
#print "c = ", c

# if len(curNode.data) > 0:
#     curNodeC = curNode.data[-1]
#     print "curNodeC = ", curNodeC

nodeInt = Node(curNode.data + "1")
nodeC = Node(curNode.data + c)

build_tree(curNode.children[0], remainingWord)
build_tree(curNode.children[1], remainingWord)

def printTree(curNode):
if curNode.children == []:
#print "curNode.data = ", curNode.data
result.append(curNode.data)
else:
printTree(curNode.children[0])
printTree(curNode.children[1])

build_tree(curNode, word)
printTree(nodeRoot)

#print "result = ", result
newResult = []
for string in result:
#print "string = ", string
newStr = ""
numOnes = 0
for c in string:
#print "c = ", c
if c != "1":
if (numOnes>0):
#print "1 numOnes = ", numOnes
newStr = newStr + str(numOnes)
numOnes = 0
newStr += c

else:
numOnes += 1

#print "2 numOnes = ", numOnes
if (numOnes > 0):
newStr = newStr + str(numOnes)
numOnes = 0
#print "newStr = ", newStr
newResult.append(newStr)

#print "newResult = ", newResult
return newResult``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.