Python List Comprehension

Python syntax 参考 https://docs.python.org/2/tutorial/datastructures.html#list-comprehensions

以Subsets为例 https://leetcode.com/problems/subsets/ dfs([1,2,3]) 应该return [ [1]+ p | all p in dfs([2,3])] + [p| all p in dfs([2,3])

class Solution(object):
    def subsets(self, nums):
        nums = sorted(nums)
        n = len(nums)
        def dfs(i):
            if i==n: return [[]]
            return [x+p for x in [[nums[i]],[]] for p in dfs(i+1)]
        return dfs(0)

https://leetcode.com/problems/subsets-ii/ 有重复元素. 将nums排序,比如[1,1,1,2,2] 转化成 [(1,3),(2,2)] (x,cnt)的形式, 那么x的出现次数是0,1..,cnt

class Solution(object):
    def subsetsWithDup(self, nums):
        n = len(nums)
        nums = sorted(nums)
        x = [0]+filter(lambda i:nums[i]!=nums[i-1], range(1,n))+[n]
        n = len(x)-1
        def subsets(i):
            if i==n: return [[]]
            cnt = x[i+1]-x[i]
            num = nums[x[i]]
            return [[num]*t+p for t in xrange(0,cnt+1) for p in subsets(i+1)]
        return subsets(0)

https://leetcode.com/problems/permutations/ Permutations perm([1,2,3]) = [ [1] + p for p in perm([2,3])] + [ [2] + p for p in perm([1,3]] + [ [3]+p for p in perm([1,2])]

class Solution(object):
    def permute(self, nums):
        def dfs(nums):
            if len(nums)==1:
                return [nums]
            v,n = set(), len(nums)
            x = [[nums[0]]+p for p in dfs(nums[1:])]
            v.add(nums[0])
            for i in xrange(1,n):
                if nums[i] in v: continue
                x += [ [nums[i]]+p for p in dfs(nums[1:i]+[nums[0]]+nums[i+1:])]
                v.add(nums[i])
            return x
        return dfs(nums)

https://leetcode.com/problems/permutations-ii/ 有重复元素的permutations 重复的元素，只有取其中一个作为第一个即可。

class Solution(object):
    def permuteUnique(self, nums):
        def dfs(nums):
            if len(nums)==1:
                return [nums]
            v,n = set(), len(nums)
            x = [[nums[0]]+p for p in dfs(nums[1:])]
            v.add(nums[0])
            for i in xrange(1,n):
                if nums[i] in v: continue
                x += [ [nums[i]]+p for p in dfs(nums[1:i]+[nums[0]]+nums[i+1:])]
                v.add(nums[i])
            return x
        return dfs(nums)

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

class Solution(object):
    def letterCombinations(self, digits):
        letter={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxzy'}
        def dfs(digits):
            if len(digits)==0: return ['']
            return [x+p for p in dfs(digits[1:]) for x in letter[digits[0]]]
        return dfs(digits) if digits else []

https://leetcode.com/problems/binary-tree-level-order-traversal/

class Solution(object):
    def levelOrder(self, root):
        def level(xs):
            if len(xs)==0: return []
            cur = map(lambda x:x.val, xs)
            return [cur] + level([j for i in xs for j in [i.left,i.right] if j])
        if root is None: return []
        return level([root])

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/ 与上面那题几乎一样。

class Solution(object):
    def levelOrderBottom(self, root):
        def level(xs):
            if len(xs)==0: return []
            cur = map(lambda x:x.val, xs)
            return level([j for i in xs for j in [i.left,i.right] if j])+ [cur]
        if root is None: return []
        return level([root])

https://leetcode.com/problems/summary-ranges/

class Solution(object):
    def summaryRanges(self, nums):
        def dfs(nums):
            if len(nums)==0: return (None,[])
            x,nums = nums[0],nums[1:]
            h,rest = dfs(nums)
            #print h,rest
            if h is None: return (x,[str(x)])
            if x+1==h:
                if '->' in rest[0]: return (x,[str(x)+rest[0][rest[0].index("->"):]]+rest[1:])
                else: return (x,[str(x)+'->'+rest[0]]+rest[1:])
            else: return (x,[str(x)]+rest)
        return dfs(nums)[1]

https://leetcode.com/problems/binary-tree-paths/

class Solution(object):
    def binaryTreePaths(self, root):
        def dfs(root): # return a list of paths  example ["2->5","3"]
            if not root: return []
            if root.left is None and root.right is None: return [str(root.val)]
            return [ str(root.val)+'->'+p for p in dfs(root.left)+dfs(root.right)]
        return dfs(root)

https://leetcode.com/problems/restore-ip-addresses/ https://github.com/Linzertorte/LeetCode-in-Python/blob/master/RestoreIPAddresses.py

class Solution(object):
    def restoreIpAddresses(self, s):
        def ok(s):
            return s=="0" or s[0]!='0' and int(s)<256
        def dfs(s,n):
            if s=="":
                return [""] if n==0 else []
            if n==0: return []
            return [ '.'+s[:i]+p for i in xrange(1,4) for p in dfs(s[i:],n-1) if i<=len(s) and ok(s[:i])]
        return map(lambda x:x[1:], dfs(s,4))

https://leetcode.com/problems/combinations/

class Solution(object):
    def combine(self, n, k):
        def dfs(i,k):
            if i==n+1:
                return [[]] if k==0 else []
            if k==0: return [[]]
            return [[j]+p for j in xrange(i,n+1) for p in dfs(j+1,k-1)]
        return dfs(1,k)

https://leetcode.com/problems/combination-sum/

class Solution(object):
    def combinationSum(self, candidates, target):
        candidates = sorted(candidates)
        n = len(candidates)
        def dfs(i,t):
            if t==0: return [[]]
            if i==n: return []
            return [x*[candidates[i]]+p for x in xrange(0,t/candidates[i]+1) for p in dfs(i+1,t-x*candidates[i]) if*candidates[i]<=t]
        return dfs(0,target)

https://leetcode.com/problems/combination-sum-ii/ 有重复元素，处理方法与Permutation II一样

class Solution(object):
    def combinationSum2(self, candidates, target):
        nums = sorted(candidates)
        n = len(nums)
        d = filter(lambda i:nums[i-1]!=nums[i], range(1,n))
        d = [0]+d+[n]
        n = len(d)-1
        # cnt d[i+1]-d[i]
        # x nums[d[i]]
        def dfs(i,t):
            if t==0: return [[]]
            if i==n: return []
            ans,x = [], nums[d[i]]
            for j in xrange(0,d[i+1]-d[i]+1):
                if j*x>t: break
                ans += [ [x]*j+p for p in dfs(i+1,t-j*x)]
            return ans
        return dfs(0,target)