998 Smallest String Starting From Leaf

h1ros

Feb 3, 2019, 10:43:19 PM

Problem Setting¶

The 2nd problem in Weekly Contest 122 is Smallest String Starting From Leaf

Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba". A leaf of a node is a node that has no children.)

Solution from Hey Shao¶

reference: Hey Shao's solution: https://leetcode.com/hanshaohey/

In [10]:

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def smallestFromLeaf(root):
    """
    :type root: TreeNode
    :rtype: str
    """
    maps={}
    letters='abcdefghijklmnopqrstuvwxyz'
    for i,l in enumerate(letters):
        maps[i]=l
    def helper(node):
        if not node.left and not node.right:
            return maps[node.val]
        elif not node.left:
            return helper(node.right)+maps[node.val]
        elif not node.right:
            return helper(node.left)+maps[node.val]
        else:
            l=helper(node.left)
            r=helper(node.right)
            ll=maps[node.val]
            return min(l+ll,r+ll)
    return helper(root)

Step-by-step solution¶

Now I am going to break down the problem and solve it step-by-step. First of all, we are aiming to pass the easiest example as below.

Example 1)

Input: [0,1,2,3,4,3,4]
Output: "dba"

Create mapping from integer to alphabet¶

this is used to convert the integer to alphabet.

In [6]:

# My solution
import string
d = {}
for x, y in zip(range(0, 26), string.ascii_lowercase):
    d[x] = y

# Hao's solution
maps={}
letters='abcdefghijklmnopqrstuvwxyz'
for i,l in enumerate(letters):
    maps[i]=l

In [3]:

maps[1]

Out[3]:

'b'

In [4]:

maps[25]

Out[4]:

'z'

Recursive function¶

Now we need to create the recursive function which returns the strings associated to the shortest path by given a node or tree. There are 4 cases for each node:

both node is null
left node is null
right note is null
both node has another tree

For cases 1~3, it is obvious to determine what is the shortest path for the given node. For case 4, we need to see which is the shortest based on the returned string from both node, which requires calling the recursive function.

Learning - `min` with `string`¶

We do not have to store the length and string at the same time. If we pass two strings to min function, the function returns the shorter one. For example,

In [7]:

min('abc', 'xyzxyz')

Out[7]:

'abc'

Execusion¶

Input: [0,1,2,3,4,3,4]

In [8]:

root = TreeNode(0)
root.left = TreeNode(1)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(4)

In [11]:

smallestFromLeaf(root)

Out[11]:

'dba'

Conclusion¶

This is the problem we need to use

mapping dictionary from integer to alphabet
recursive function to return the strings matched with the shorted path
implement 4 possible cases for each node