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


  • 0
    W

    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)
    
                curNode.add_child(nodeInt)
                curNode.add_child(nodeC)
    
                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

Log in to reply
 

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