E-784. Letter Case Permutation

Loading...LeetCode

这道题很interesting。

# experiments for deque
from collections import deque
a='123'
b = [a]
c = [[a]]


d = deque(a)
d_pop= d.popleft()
print(d)
print(d_pop)
print(type(d_pop))

e = deque(b)
e_pop= e.popleft()
print(e)
print(e_pop)
print(type(e_pop))

f = deque(c)
f_pop= f.popleft()
print(f)
print(f_pop)
print(type(f_pop))

# 感觉这是一个不容易引起误解的初始化方法
g = deque([])
g.append(a)
print(g)
g_pop= g.popleft()
print(g)
print(g_pop)
print(type(g_pop))
"""
deque(['2', '3'])
1
<type 'str'>

deque([])
123
<type 'str'>

deque([])
['123']
<type 'list'>

deque(['123'])
deque([])
123
<type 'str'>
"""

# BFS
# translated from java solution: https://leetcode.com/problems/letter-case-permutation/discuss/115485/Java-Easy-BFS-DFS-solution-with-explanation
# O(N*2^N), O(N*2^N)这个时间复杂度挺有意思，稍微不小心就会遗漏掉N.
from collections import deque
class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        if not S:
            return []
        q = deque([S])
        
        for i in range(len(S)):
            if S[i].isdigit(): continue
            cur_lvl_size = len(q)
            for j in range(cur_lvl_size):
                cur = q.popleft()
                lower_case_str = cur[:i]+cur[i].lower()+cur[i+1:]
                upper_case_str = cur[:i]+cur[i].upper()+cur[i+1:]
                q.append(lower_case_str)
                q.append(upper_case_str)
        return list(q)

# DFS
class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        def dfs(res, per_str, pos):
            if pos >= len(per_str):
                res.append(per_str)
            elif per_str[pos].isdigit():
                dfs(res, per_str, pos + 1)
            else:
                lower_case_str = per_str[:pos] + per_str[pos].lower() + per_str[pos+1:]
                dfs(res, lower_case_str, pos + 1)

                upper_case_str = per_str[:pos] + per_str[pos].upper() + per_str[pos+1:]
                dfs(res, upper_case_str, pos + 1)
            
        if not S:
            return []
        res = []
        dfs(res, S, 0)
        return res