Leetcode # 784. Letter Case Permutation

https://leetcode.com/problems/letter-case-permutation/

Solution

Time Complexity = Space Complexity = O(len(s) * 2 ^ len(s))

class Solution:
  def letterCasePermutation(self, s: str) -> List[str]:
    f = lambda x: (x.lower(), x.upper()) if x.isalpha() else x
    return map("".join, itertools.product(*map(f, s)))

map(function, iterable, …)

將function套用在每個iterable中的value
傳回的物件可用list()、set()…等，轉換為所需要的物件型別

f = lambda x: (x.lower(), x.upper()) if x.isalpha() else x
list(map(f, "a1b2"))⇒[(a, A), 1, (b, B), 2]

itertools.product(*iterables, repeat=1)

回傳笛卡兒積 (Cartesian product)：
$$X \times Y := \{(x, y) \mid x \in X \land y \in Y \}$$

相當於：

def product(*iterables, repeat=1):
  pools = [tuple(pool) for pool in iterables] * repeat
  result = [[]]
  for pool in pools:
    result = [x + [y] for x in result for y in pool]
  for prod in result:
    yield tuple(prod)

承接上述的map(f, "a1b2")
itertools.product(*map(f, "a1b2"))中：

• pools：[('a', 'A'), ('1',), ('b', 'B'), ('2',)]
• result：
  [['a', '1', 'b', '2'], 
 ['a', '1', 'B', '2'],
 ['A', '1', 'b', '2'],
 ['A', '1', 'B', '2']]

最後利用"".join()將 result 中的每個 list 轉換為 str

Unpacking（解包）

利用*(asterisk/star) 將map物件解包為*iterables

只有一個 element（元素）的 tuple（元組）

只有一個元素的 tuple 必須標示為 (x, )

例：

• (1, 2, 3) + (4)是一個元組和一個整數 (int) 做+運算
  ⇒ 會導致型別錯誤 (TypeError)
• (1, 2, 3) + (4, )則是串接兩個元組成為(1, 2, 3, 4)

關於 yield

使用return回傳，將會使函式結束

使用yield表達式配合for迴圈（自帶__next__()）能製作 generator：
yield回傳之後，所屬函式將會被暫停；
當__next__()被呼叫後，會回覆暫停狀態繼續執行

Last Updated on 2023/08/16 by A1go