Letter Case Permutation

# 問題

アルファベットと数字で構成される文字列が与えられる．任意のアルファベットについて大文字小文字に変換できる．この変換によって得られるすべての文字列を計算せよ．

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

# 答え

DFS．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        ret = []
        def rec(pos, sofar):
            if pos == len(S):
                ret.append(sofar)
                return
            if S[pos].isalpha():
                rec(pos + 1, sofar + S[pos])
                rec(pos + 1, sofar + S[pos].swapcase())
            else:
                rec(pos + 1, sofar + S[pos])
        rec(0, "")
        return ret