Python Tricks - Iterable - Part 2

      map(function, iterables) -> iterables
    

      """map to node children recursively"""
# L104: get depth in binary tree
def max_depth(root: TreeNode) -> int:
    return 1 + max(map(maxDepth, (root.left, root.right))) if root else 0

"""comparison map find with map index"""
# L290: given a pattern and a string words, find if words follows the same pattern. 
# i.e. pattern = 'abba', words = 'dog cat cat dog'
def valid_word_pattern(pattern: str, words: str) -> bool:
    s, t = pattern, words.split()
    return list(map(s.find, s)) == list(map(t.index, t))

"""map dict.get"""
# L506: given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal"
def find_relative_ranks(nums: List[int]) -> List[str]:
    sorted_nums = sorted(nums, reverse=True)
    rank = ["Gold Medal", "Silver Medal", "Bronze Medal"] + list(map(str, range(4, len(nums) + 1)))
    return list(map(dict(zip(sorted_nums, rank)).get, nums))
    

      reduce(function, sequence[, initial]) -> value
    

      # L136: every numbers appears twice except for one, find that single one
def single_number(nums: List[int]) -> int:
    return reduce(lambda x, y: x ^ y, nums)

# L47: generate all possible permutations
def permute(nums: List[int]) -> List[List[int]]:
    return reduce(lambda P, n: [p[:i] + [n] + p[i:] for p in P for i in range(len(p)+1)], nums, [[]])
    

      zip(*iterables) -> iterator
    

      a = [1,2,3]
b = ['one','two','three']
zipped=zip(a,b)
list(zipped)
# output: [(1, 'one'), (2, 'two'), (3, 'three')]
    

      """construct dict"""
keys = ['a', 'b', 'c']
vals = [1, 2, 3]
zipped_dict = dict(zip(keys, vals))

"""difference of neighbor pairs"""
arr, diffs = [1, 2, 3, 4, 5], []
for pre, post in zip(arr[:-1], arr[1:]):  # zip(arr, arr[1:]) is ok too, zip matches the shortest
    diffs.append(post - pre)

"""transpose matrix"""
# L867: The transpose of a matrix is the matrix flipped over it's main diagonal, switching the row and column indices of the matrix.
def transpose(matrix: List[List[int]]) -> List[List[int]]:
    return list(map(list, zip(*matrix)))

"""zip into a set"""
# L290: given a pattern and a string words, find if words follows the same pattern. 
# i.e. pattern = 'abba', words = 'dog cat cat dog'
def valid_word_pattern(pattern: str, words: str) -> bool:
    s, t = pattern, words.split()
    return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)
    

      def product(a, b):
    return a * b

"""use * to unpack tuple, list or other iterables"""
param_tuple = (2, 3)
product(*param_tuple)
# output: 6

"""use ** to unpack dict"""
param_dict = {'a': 2, 'b': 3}
product(**param_dict)
# output: 6
    

      """get rest of all"""
a, *b, c = range(5)
# b = [1, 2, 3]
[(c, *d, [*e]), f, *g] = [[1, 2, 3, 4, [5, 5, 5]], 6, 7, 8]
# d = [2, 3, 4], e = [5, 5, 5], g = [7, 8]

"""merge dicts"""
a = {'1': 1, '2': 2}
b = {'2': 3, '4': 4}
merged_dict = {**a, **b}   #{'1': 1, '2': 3, '4': 4}

"""[*a] = list(a), [*zip(*matrix)]: transpose matrix"""
# L54: traverse matrix in spiral order.
def traverse_spiral_order(matrix: List[List[int]]) -> List[int]:
    return matrix and [*matrix.pop(0)] + traverse_spiral_order([*zip(*matrix)][::-1])
    

      sum(iterable[, start]) -> number
    

      """sum"""
# L771: S is stones you have, J is types of stones which are jewels, and you want to know how many stones are also jewels.
def num_jewels_in_stones(J: str, S: str) -> int:
    return sum(map(J.count, S))

# L389: string t is generated by random shuffling string s and then add one more letter at a random position, find the letter.
def find_the_difference(s: str, t: str) -> str:
    return chr(sum(map(ord, t)) - sum(map(ord, s)))

# L266: determine if a permutation of the string could form a palindrome
def can_permute_palindrome(s: str) -> bool:
    """at most one odd count character"""
    return sum(v % 2 for v in Counter(s).values()) <= 1
    

      max(iterable[, default=obj, key=func]) -> value
    

      """max"""
# L169: find the majority element which appears more than ⌊ n/2 ⌋ times.
def majority_element(nums: List[int]) -> int:
    counts = Counter(nums)
    return max(counts.keys(), key=counts.get)

"""min"""
# L14: find the longest common prefix string amongst an array of strings.
def longest_common_prefix(strs: List[str]) -> str:
    shortest = min(strs, key=len)
    for i, ch in enumerate(shortest):
        if any(s[i] != ch for s in strs):
            return shortest[:i]
    return shortest
    

      any(iterable) -> bool
    

      """any"""
# L36: determine if a 9x9 Sudoku board is valid, which means 1-9 in row, column, 3x3 sub-boxes
def is_valid_sudoku(board: List[List[str]]) -> bool:
    seen = set()
    return not any(x in seen or seen.add(x)
                   for i, row in enumerate(board)
                   for j, c in enumerate(row)
                   if c != '.'
                   for x in ((c, i), (j, c), (i/3, j/3, c)))

"""all"""
# L766: a matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
def is_toeplitz_matrix(matrix: List[List[int]]) -> bool:
    return all(r == 0 or c == 0 or matrix[r-1][c-1] == val
               for r, row in enumerate(matrix)
               for c, val in enumerate(row))

# L246: verify the number is strobogrammatic, strobogrammatic number looks the same when rotated 180 degrees
def is_strobogrammatic(num: str) -> bool:
    return all(map('696 00 11 88'.count, map(operator.add, num, num[::-1])))

# L261: given n nodes labeled from 0 to n-1 and a list of undirected edges, check whether these edges make up a valid tree.
def valid_tree(n: int, edges: List[List[int]]) -> bool:
    """all check in union find"""
    parent = range(n)
    def find(x):
        return x if parent[x] == x else find(parent[x])
    def union(xy):
        x, y = map(find, xy)
        parent[x] = y
        return x != y
    return len(edges) == n-1 and all(map(union, edges))
    

      bisect.bisect_left(a, x[, lo=0, hi=len(a)]) -> int
    

      """use binary search to find the first number that's less than or equal to the last."""
# L153: find the minimum element in rotated sorted array
def find_min_in_rotated_sorted_arr(self, nums: List[int]) -> int:
    """construct iterable which distinguish the two parts of rotated array"""
    self.__getitem__ = lambda i: nums[i] <= nums[-1]
    return nums[bisect.bisect(self, False, 0, len(nums))]

"""construct a boolean iterable and use binary search"""
# L4: find the median of the two sorted arrays
def find_median_in_two_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
    a, b = sorted((nums1, nums2), key=len)
    m, n = len(a), len(b)
    after = (m + n - 1) // 2
    class Range:
        def __getitem__(self, i):
            return after-i-1 < 0 or a[i] >= b[after-i-1]
    i = bisect.bisect_left(Range(), True, 0, m)
    nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
    return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2