LeetCode algorithm problems

add-binary.py

class Solution:
    # @param {string} a
    # @param {string} b
    # @return {string}
    def addBinary(self, a, b):
        return bin(long(a, 2) + long(b, 2))[2:]

anagrams.py

class Solution:
    # @param {string[]} strs
    # @return {string[]}
    def anagrams(self, strs):
        retval = {}
        for item in strs:
            retval.setdefault(''.join(sorted(item)), []).append(item)
        return [item for col in retval.values() if len(col) > 1 for item in col]

balanced-binary-tree.py

class Solution:
    # @param {TreeNode} root
    # @return {boolean}
    def isBalanced(self, root):
        def height(root):
            if root is None:
                return 0, True
            elif root.left is None and root.right is None:
                return 1, True
            else:
                lheight, lbalanced = height(root.left)
                rheight, rbalanced = height(root.right)
                if lbalanced and rbalanced:
                    return max(lheight, rheight) + 1, abs(lheight - rheight) <= 1
                else:
                    return max(lheight, rheight) + 1, False

        return height(root)[1]

binary-search-tree-iterator.py

class BSTIterator:
    def __init__(self, root):
        self.root = root

        def dfs(root):
            return dfs(root.left) + [root.val] + dfs(root.right) if root else []

        self.cache = dfs(root)

    def hasNext(self):
        return len(self.cache) != 0

    def next(self):
        val = self.cache[0]
        del self.cache[0]
        return val

binary-tree-inorder-traversal.py

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def inorderTraversal(self, root):
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) if root else []

binary-tree-level-order-traversal-ii.py

class Solution:
    # @param {TreeNode} root
    # @return {integer[][]}
    def levelOrderBottom(self, root):
        ans = []

        def travel(root, deepth):
            if root:
                while len(ans) <= deepth:
                    ans.append([])
                ans[deepth].append(root.val)
                travel(root.left, deepth + 1)
                travel(root.right, deepth + 1)

        travel(root, 0)
        return ans[::-1]

binary-tree-level-order-traversal.py

class Solution:
    # @param {TreeNode} root
    # @return {integer[][]}
    def levelOrder(self, root):
        ans = []

        def travel(root, deepth):
            if root:
                while len(ans) <= deepth:
                    ans.append([])
                ans[deepth].append(root.val)
                travel(root.left, deepth + 1)
                travel(root.right, deepth + 1)

        travel(root, 0)
        return ans

binary-tree-postorder-traversal.py

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def postorderTraversal(self, root):
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val] if root else []

binary-tree-preorder-traversal.py

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def preorderTraversal(self, root):
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) if root else []

climbing-stairs.py

class Solution:
    # @param {integer} n
    # @return {integer}
    def climbStairs(self, n):
        if n not in self.cache:
            self.cache[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2) if n > 1 else 1
        return self.cache[n]

    def __init__(self):
        self.cache = {}

compare-version-numbers.py

class Solution:
    # @param {string} version1
    # @param {string} version2
    # @return {integer}
    def compareVersion(self, version1, version2):
        def convert(version):
            retval = map(int, version.split('.'))
            while len(retval) > 1 and retval[-1] == 0:
                del retval[-1]
            return retval

        return cmp(convert(version1), convert(version2))

contains-duplicate.py

class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def containsDuplicate(self, nums):
        return len(set(nums)) != len(nums)

convert-sorted-array-to-binary-search-tree.py

class Solution:
    # @param {integer[]} nums
    # @return {TreeNode}
    def sortedArrayToBST(self, nums):
        size = len(nums)
        if size:
            node = TreeNode(nums[size / 2])
            node.left = self.sortedArrayToBST(nums[:size / 2])
            node.right = self.sortedArrayToBST(nums[size / 2 + 1:])
            return node
        else:
            return None

count-and-say.py

import itertools


class Solution:
    # @param {integer} n
    # @return {string}
    def countAndSay(self, n):
        retval = '1'
        for _ in range(n - 1):
            retval = ''.join('{count}{value}'.format(count=len(list(value)), value=key)
                             for key, value in itertools.groupby(retval))
        return retval

course-schedule.py

class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        graph, degree = {}, {}
        for u, v in prerequisites:
            degree[v] = degree.get(v, 0) + 1
            graph[u] = graph.get(u, []) + [v]
        zeros = [u for u in range(numCourses) if u not in degree]
        while len(zeros):
            u, zeros, numCourses = zeros[0], zeros[1:], numCourses - 1
            for v in graph.get(u, []):
                degree[v] -= 1
                if degree[v] == 0:
                    zeros.append(v)
        return numCourses == 0

decode-ways.py

class Solution:
    # @param {string} s
    # @return {integer}
    def numDecodings(self, s):
        cache = {}
        s = s.strip()

        def decode(index):
            if index not in cache:
                if index >= len(s):
                    cache[index] = 1
                elif s[index] == '0':
                    cache[index] = 0
                elif s[index] == '1' and index + 1 < len(s):
                    cache[index] = decode(index + 1) + decode(index + 2)
                elif s[index] == '2' and index + 1 < len(s) and s[index + 1] < '7':
                    cache[index] = decode(index + 1) + decode(index + 2)
                else:
                    cache[index] = decode(index + 1)
            return cache[index]

        return decode(0) if s else 0

excel-sheet-column-number.py

class Solution:
    # @param {string} s
    # @return {integer}
    def titleToNumber(self, s):
        return sum((ord(chr) - ord('A') + 1) * (26 ** index) for index, chr in enumerate(s[::-1]))

excel-sheet-column-title.py

class Solution:
    # @param {integer} n
    # @return {string}
    def convertToTitle(self, n):
        return (self.convertToTitle((n - 1) / 26) if n > 26 else '') + chr((n - 1) % 26 + ord('A'))

find-minimum-in-rotated-sorted-array.py

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def findMin(self, nums):
        def binary(left, right, nums):
            if nums[left] <= nums[right]:
                return nums[left]
            else:
                if nums[left] <= nums[(left + right) / 2]:
                    return binary((left + right) / 2 + 1, right, nums)
                else:
                    return binary(left, (left + right) / 2, nums)

        return binary(0, len(nums) - 1, nums)

generate-parentheses.py

class Solution:
    # @param {integer} n
    # @return {string[]}
    def generateParenthesis(self, n):
        def generate(ans, open, close):
            if open == 0 and close == 0:
                yield ans
            else:
                if open:
                    for parenthesis in generate(ans + '(', open - 1, close):
                        yield parenthesis
                if close and open < close:
                    for parenthesis in generate(ans + ')', open, close - 1):
                        yield parenthesis

        return [parenthesis for parenthesis in generate('(', n - 1, n)]

length-of-last-word.py

class Solution:
    # @param {string} s
    # @return {integer}
    def lengthOfLastWord(self, s):
        return len(s.strip().split()[-1]) if s.strip() else 0

linked-list-cycle.py

class Solution:
    # @param head, a ListNode
    # @return a boolean
    def hasCycle(self, head):
        while head:
            if getattr(head, 'visited', False):
                return True
            else:
                head.visited = True
                head = head.next
        return False

longest-common-prefix.py

class Solution:
    # @param {string[]} strs
    # @return {string}
    def longestCommonPrefix(self, strs):
        def check(*strs):
            for step in zip(*strs):
                if len(set(step)) == 1:
                    yield step[0]
                else:
                    break

        return ''.join(check(*strs))

majority-element.py

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def majorityElement(self, nums):
        retval = {}
        for num in nums:
            retval[num] = retval.get(num, 0) + 1
        return max(retval.items(), key=lambda (key, value): value)[0]

maximum-depth-of-binary-tree.py

class Solution:
    # @param {TreeNode} root
    # @return {integer}
    def maxDepth(self, root):
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 if root else 0

maximum-subarray.py

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def maxSubArray(self, nums):
        ans, now = nums[0], 0
        for num in nums:
            now = max(num, now + num)
            ans = max(ans, now)
        return ans

merge-two-sorted-lists.py

class Solution:
    # @param {ListNode} l1
    # @param {ListNode} l2
    # @return {ListNode}
    def mergeTwoLists(self, l1, l2):
        if l1 and l2:
            if l1.val < l2.val:
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1, l2.next)
                return l2
        else:
            return l1 or l2

minimum-depth-of-binary-tree.py

class Solution:
    # @param {TreeNode} root
    # @return {integer}
    def minDepth(self, root):
        if root is None:
            return 0
        elif root.left is None and root.right is None:
            return 1
        elif root.left is None or root.right is None:
            return (self.minDepth(root.left) if root.left else self.minDepth(root.right)) + 1
        else:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

minimum-path-sum.py

class Solution:
    # @param {integer[][]} grid
    # @return {integer}
    def minPathSum(self, grid):
        cache = {}

        def dfs(x, y):
            if (x, y) not in cache:
                cache[x, y] = min(dfs(a, b) + grid[x][y]
                                  for a, b in [(x - 1, y), (x, y - 1)] if a >= 0 and b >= 0) if x or y else grid[x][y]
            return cache[x, y]

        return dfs(len(grid) - 1, len(grid[0]) - 1)

n-queens-ii.py

class Solution:
    # @param {integer} n
    # @return {integer}
    def totalNQueens(self, n):
        def solve(row, state):
            if row == n:
                return 1
            else:
                ans = 0
                for column in range(n):
                    for a, b in state:
                        if column == b or abs(row - a) == abs(column - b):
                            break
                    else:
                        ans += solve(row + 1, state + [(row, column)])
                return ans

        return solve(0, [])

n-queens.py

class Solution:
    # @param {integer} n
    # @return {integer}
    def solveNQueens(self, n):
        def solve(row, state):
            if row == n:
                return [state]
            else:
                ans = []
                for column in range(n):
                    for a, b in state:
                        if column == b or abs(row - a) == abs(column - b):
                            break
                    else:
                        ans += solve(row + 1, state + [(row, column)])
                return ans

        retval = []
        for solution in solve(0, []):
            ans = [['.'] * n for _ in range(n)]
            for x, y in solution:
                ans[x][y] = 'Q'
            retval.append([''.join(row) for row in ans])
        return retval

number-of-1-bits.py

class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        return self.hammingWeight(n / 2) + (1 if n % 2 == 1 else 0) if n else 0

path-sum.py

class Solution:
    # @param {TreeNode} root
    # @param {integer} sum
    # @return {boolean}
    def hasPathSum(self, root, sum):
        if root is None:
            return False
        elif root.left is None and root.right is None:
            return sum == root.val
        else:
            return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

permutations.py

class Solution:
    # @param {integer[]} nums
    # @return {integer[][]}
    def permute(self, nums):
        return [[nums[i]] + permutation
                for i in range(len(nums))
                for permutation in self.permute(nums[:i] + nums[i + 1:])] if len(nums) else [[]]

plus-one.py

class Solution:
    # @param {integer[]} digits
    # @return {integer[]}
    def plusOne(self, digits):
        return [int(c) for c in str(int(''.join(map(str, digits))) + 1)]

populating-next-right-pointers-in-each-node.py

import itertools

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        queue = [root]
        while len(queue) != 0:
            offspring = []
            for a, b in itertools.izip_longest(queue, queue[1:]):
                if a:
                    a.next = b
                    offspring += [a.left, a.right]
            queue = offspring

powx-n.py

class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if x == 0:
            return 0
        elif n == 0:
            return 1
        elif n < 0:
            return 1.0 / self.myPow(x, -n)
        else:
            ans = self.myPow(x, n / 2)
            return (ans * ans) if n % 2 == 0 else (ans * ans * x)

remove-duplicates-from-sorted-array.py

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def removeDuplicates(self, nums):
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] == nums[i - 1]:
                del nums[i]
        return len(nums)

remove-duplicates-from-sorted-list.py

class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def deleteDuplicates(self, head, state=set([])):
        if head:
            if head.val in state:
                return self.deleteDuplicates(head.next, state)
            else:
                head.next = self.deleteDuplicates(head.next, state | set([head.val]))
        return head

remove-element.py

class Solution:
    # @param {integer[]} nums
    # @param {integer} val
    # @return {integer}
    def removeElement(self, nums, val):
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] == val:
                del nums[i]
        return len(nums)

reverse-bits.py

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        return int('{:032b}'.format(n)[::-1], 2)

reverse-integer.py

class Solution:
    # @param {integer} x
    # @return {integer}
    def reverse(self, x):
        retval = int(str(abs(x))[::-1]) * (-1 if x < 0 else 1)
        return retval if retval.bit_length() < 32 else 0

reverse-linked-list.py

class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def reverseList(self, head, prev=None):
        if head:
            head.next, head = prev, self.reverseList(head.next, head) if head.next else head
        return head

rotate-image.py

class Solution:
    # @param {integer[][]} matrix
    # @return {void} Do not return anything, modify matrix in-place instead.
    def rotate(self, matrix):
        matrix[:] = list(zip(*reversed(matrix)))

same-tree.py

class Solution:
    # @param {TreeNode} p
    # @param {TreeNode} q
    # @return {boolean}
    def isSameTree(self, p, q):
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return p is None and q is None

search-insert-position.py

import bisect


class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer}
    def searchInsert(self, nums, target):
        return bisect.bisect_left(nums, target)

single-number.py

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        return reduce(lambda x, y: x ^ y, nums)

sort-colors.py

class Solution:
    # @param {integer[]} nums
    # @return {void} Do not return anything, modify nums in-place instead.
    def sortColors(self, nums):
        a = filter(lambda num: num == 0, nums)
        b = filter(lambda num: num == 1, nums)
        c = filter(lambda num: num == 2, nums)
        nums[:] = a + b + c

swap-nodes-in-pairs.py

class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def swapPairs(self, head):
        if head and head.next:
            head.val, head.next.val = head.next.val, head.val
            self.swapPairs(head.next.next)
        return head

symmetric-tree.py

class Solution:
    # @param {TreeNode} root
    # @return {boolean}
    def isSymmetric(self, root):
        def bfs(roots):
            vals = [root.val if root else None for root in roots]
            return vals == vals[::-1] and bfs(
                reduce(lambda ans, root: ans + ([root.left, root.right] if root else []), roots, [])) if roots else True

        return bfs([root])

two-sum.py

class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer[]}
    def twoSum(self, nums, target):
        retval = {}
        for index, num in enumerate(nums):
            if target - num in retval:
                return retval[target - num][0] + 1, index + 1
            else:
                retval.setdefault(num, []).append(index)

unique-binary-search-trees.py

class Solution:
    def __init__(self):
        self.cache = {}

    # @param {integer} n
    # @return {integer}
    def numTrees(self, n):
        def count(n):
            if n not in self.cache:
                self.cache[n] = sum(self.numTrees(a) * self.numTrees(n - a - 1) for a in range(0, n)) if n > 1 else 1
            return self.cache[n]

        return count(n)

unique-paths-ii.py

class Solution:
    # @param {integer[][]} obstacleGrid
    # @return {integer}
    def uniquePathsWithObstacles(self, obstacleGrid):
        cache = {(0, 0): 1 if obstacleGrid[0][0] == 0 else 0}

        def dfs(x, y):
            if (x, y) not in cache:
                cache[x, y] = sum(dfs(a, b) for a, b in [(x - 1, y), (x, y - 1)] if a >= 0 and b >= 0) if obstacleGrid[x][y] == 0 else 0
            return cache[x, y]

        return dfs(len(obstacleGrid) - 1, len(obstacleGrid[0]) - 1)

unique-paths.py

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        def factorial(a):
            return reduce(lambda x, y: x * y, range(1, a + 1))

        return factorial(m + n - 2) / factorial(n - 1) / factorial(m - 1) if n > 1 and m > 1 else 1

valid-number.py

import re


class Solution:
    # @param {string} s
    # @return {boolean}
    def isNumber(self, s):
        return re.match(r'^[+-]?((\d+(\.\d*)?)|(\d*\.\d+))([eE][+-]?\d+)?$', s.strip()) != None

valid-palindrome.py

class Solution:
    # @param {string} s
    # @return {boolean}
    def isPalindrome(self, s):
        s = filter(lambda chr: chr.isdigit() or chr.isalpha(), s.lower())
        return s == s[::-1]

valid-parentheses.py

class Solution:
    # @param {string} s
    # @return {boolean}
    def isValid(self, s):
        def match(a, b):
            return a == '(' and b == ')' or a == '{' and b == '}' or a == '[' and b == ']'

        return reduce(lambda stack, item: stack[:-1] if match(stack[-1], item) else stack + [item], s, [None]) == [None]

zigzag-conversion.py

class Solution:
    # @param {string} s
    # @param {integer} numRows
    # @return {string}
    def convert(self, s, numRows):
        ans, row, numColumns, state = {}, 0, 0, 'a'
        for char in s:
            ans[row, numColumns] = char
            if state == 'a':
                row += 1
                if row == numRows - 1:
                    state = 'b'
            elif state == 'b':
                row -= 1
                numColumns += 1
                if row == 0:
                    state = 'a'

        return ''.join(c for (_, c) in sorted(ans.items()))