Python O(n) DFS


  • 1
    class Solution(object):
        def parseTernary(self, expression):
            """
            :type expression: str
            :rtype: str
            """
            stack = []
            d = {}
            for i in xrange(0, len(expression)):
                if expression[i] == "?":
                    stack.append(("?", i))
                elif expression[i] == ":":
                    _, pos = stack.pop()
                    d[pos] = i
    
            def dfs(expr, start, end, d):
                if end - start + 1 < 5:
                    return expr[start:end+1]
                iSep = d[start + 1]
                stmt = expr[start]
                return dfs(expr, start + 2, iSep - 1, d) if stmt == "T" else dfs(expr, iSep + 1, end, d)
            return dfs(expression, 0, len(expression), d)
    

Log in to reply
 

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