All Articles

Leetcode Contest 140

Letter Tile Possibilities

You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.

Keyword: permutation

  • Sort not needed
  • Use a helper method to iterate over all possibilities, use set to avoid repetition

Similar to: 47. Permutations II

class Solution(object):
    def numTilePossibilities(self, tiles):
        """
        :type tiles: str
        :rtype: int
        """
        record = set()

        def helper(currString, remainingCharacters):
            if len(remainingCharacters) == 0:
                record.add(currString)
                return
            if currString in record:
                return
            record.add(currString)
            for i in range(len(remainingCharacters)):
                helper(currString + remainingCharacters[i], remainingCharacters[:i] + remainingCharacters[i+1:])

        helper("", tiles)
        print record, len(record)
        return len(record) - 1

Another one line brute force solution from discuss:

    def numTilePossibilities(self, S):
        return len({s[:i] for s in itertools.permutations(S) for i in xrange(8)})

Insufficient Nodes in Root to Leaf Paths

Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf. (A leaf is a node with no children.) A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit. Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

Keyword: Tree, DFS, recursive

  • I didn’t pass this question due to one very long test case failure.
  • However the solution won’t be too different, so I consider it solved 😂

Recursive solution:

class Solution(object):
    def sufficientSubset(self, root, limit):
        """
        :type root: TreeNode
        :type limit: int
        :rtype: TreeNode
        """
        if root == None: return None
        if root.left == None and root.right == None:
            return root if root.val >= limit else None
        if root.left != None:
            root.left = self.sufficientSubset(root.left, limit - root.val)
        if root.right != None:
            root.right = self.sufficientSubset(root.right, limit - root.val)
        return root

Smallest Subsequence of Distinct Characters

Return the lexicographically smallest subsequence of text that contains all the distinct characters of text exactly once.

Keyword: Greedy

  • Same as Remove Duplicate Letters
  • Idea: when met a new character c, if the last item in our current result is larger than c, and the last item still remains later, then we remove it for now.
  • A very nice solution explained: link
class Solution(object):
    def smallestSubsequence(self, text):
        """
        :type text: str
        :rtype: str
        """
        record = {}
        for index, c in enumerate(text):
            record[c] = index
        print record

        result = []
        for index, c in enumerate(text):
            if c in result:
                continue
            while len(result) > 0 and result[-1] > c and record[result[-1]] > index:
                # if the last character is larger than c, and the character still remains in text, remove it
                result.pop()
            result.append(c)
        return ''.join(result)

Published Jun 9, 2019

Software Engineer at Facebook. Loves football, volunteering, and exploring the world.