class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits: return []
        res = ['']
        nums =  list(digits)
        d = {'2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'], '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'
], '7': ['p', 'q', 'r', 's'], '8': ['t', 'u', 'v'], '9': ['w', 'x', 'y', 'z']}
        for n in digits:
            lst = d[n]
            new_res = []
            for char in lst:
                for string in res:
                    new_res.append(string + char)
            res = new_res
        return res

In [347]: s = Solution(); t = s.letterCombinations('23')
In [349]: print(t)
['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        queue = [root]
        res = []
        level = 0
        while queue:
            level += 1
            temp = []
            tempq = []
            for node in queue:
                temp.append(node.val)
                if node.left:
                    tempq.append(node.left)
                if node.right:
                    tempq.append(node.right)
            queue = tempq
            if level % 2 == 0 :
                temp = temp[::-1]
            res.append(temp)
        return res

import math
class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        s = [i*i for i in range(1,int(math.sqrt(n))+1)] # Square numbers <= n
        l = 0  # BFS level
        currentLevel = [0]  # List of numbers in BFS level l
        while True:
            nextLevel = []
            for a in currentLevel:
                for b in s:
                    if a+b == n: return l+1  # Found n
                    if a+b < n:  nextLevel.append(a+b)
            currentLevel = list(set(nextLevel))  # Remove duplicates
            l += 1

class Solution:
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        first = second = float('inf')
        for x in nums:
            if x <= first:
                first = x
            elif x <= second:
                second = x
            else:
                return True
        return False

class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tails = [0] * len(nums)
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                m = (i + j) // 2
                if tails[m] < x:
                    i = m + 1
                else:
                    j = m
            print(i, j, size, x)
            tails[i] = x
            size = max(i + 1, size)
            print(size, tails)
        return size