"""construct iterator to make sure check every char only once by 'in' """
# L392: check if s is subsequence of t. s = "abc", t = "ahbgdc", return true.
def is_subsequence(s: str, t: str) -> bool:
    t = iter(t)
    return all(c in t for c in s)
    

      """generate all combinations of coins which sum to target amount"""
def get_coin_changes(coins: List[int], amount[int]) -> List[List[int]]:
    for i, coin in enumerate(coins):
        if coin == amount:
            yield (coin,)
        elif coin < amount:
            yield from ((coin,) + x for x in change(coins[i:], amount - coin))

"""generate all combinations of well-formed n pairs of parentheses"""
# L22: generate all combinations of well-formed n pairs of parentheses.
def generate_parenthesis(n: int) -> List[str]:
    def generate(p, left, right):
        if 0 <= left <= right:
            if not right:
                yield p
            for q in generate(p + '(', left-1, right): yield q
            for q in generate(p + ')', left, right-1): yield q
    return list(generate('', n, n))
    

      """list comprehension"""
odds_list = [x for x in range(20) if x % 2]

"""generator_expression"""
odds_generator = (x for x in range(20) if x % 2)

"""set comprehension"""
odds_set = {x for x in range(20) if x % 2}

"""dict comprehension"""
square_dict = {x: x**2 for x in range(10)}
    

      """bfs in list comprehension way"""
# L515: find the largest value in each row of a binary tree
def find_largest_in_binary_tree_rows(root: TreeNode) -> List[int]:
    maxes, row = [], [root]
    while any(row):
        maxes.append(max(node.val for node in row))
        row = [kid for node in row for kid in (node.left, node.right) if kid]
    return maxes

"""rotate image by list comprehension"""
# L48: rotate the image by 90 degrees (clockwise)
def rotate_image_90_degrees(matrix: List[List[int]]) -> None:
    matrix[:] = [[row[i] for row in matrix[::-1]] for i in range(len(A))]

"""generate combinations by list comprehension recursively"""
# L77: Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
def combine(n: int, k: int) -> List[List[int]]:
    if k == 0:
        return [[]]
    # add last element
    return [pre + [i] for i in range(k, n + 1) for pre in combine(i - 1, k - 1)]

"""generate binary trees by list comprehension recursively"""
# given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
def generate_binary_search_trees(last: int, first: int=1) -> List[TreeNode]:
    def node(val, left, right):
        node = TreeNode(val)
        node.left = left
        node.right = right
        return node
    return [node(root, left, right) 
            for root in range(first, last+1)
            for left in generate_binary_search_trees(root-1, first)
            for right in generate_binary_search_trees(last, root+1)] or [None]
    

      lambda arguments : expression
    

      """lambda used in lexical closure"""
def make_adder(n):
    return lambda x: x + n

plus_3 = make_adder(3)
plus_3(4)
# output: 7

"""lambda used in key"""
# sort dict by value
d = {'apple': 18, 'orange': 20, 'banana': 5, 'rotten tomato': 1}
sorted(d.items(), key=lambda x: x[1])
# alternative
from operator import itemgetter
sorted(d.items(), key=itemgetter(1))
# output: [('rotten tomato', 1), ('banana', 5), ('apple', 18), ('orange', 20)]

for pos in range(len(S)):
    """lambda used in filter"""
    matched_words = list(filter(lambda x: S[pos:].startswith(x), words))
    if matched_words:
        """lambda used in max"""
        add_interval([pos, pos + len(max(matched_words, key=lambda x: len(x)))])

"""call lambda in nested"""
# L422: given a sequence of words, check whether it forms a valid word square.
def valid_word_square(words: List[str]) -> bool:
    f = lambda x: map(None, *x)  # python 2
    return f(f(words)) == f(words)

"""use lambda to wrap parameter as callable"""
def wrapped_callable(f):
    if callable(f): return f
    else: return lambda: f