0784. 字母大小写全排列 #

标签：位运算、字符串、回溯
难度：中等

题目大意 #

给定一个字符串s，通过将字符串s中的每个字母转变大小写，我们可以获得一个新的字符串。

要求：返回所有可能得到的字符串集合。

解题思路 #

回溯算法进行求解。具体解法如下：

i 代表当前要处理的字符在字符串 s 中的下标，path 表示当前路径，ans 表示答案数组。
如果处理到 i == len(s) 时，将当前路径存入答案数组中返回，否则进行递归处理。
- 不修改当前字符，直接递归处理第 i + 1 个字符。
- 如果当前字符是小写字符，则变为大写字符之后，递归处理第 i + 1 个字符。
- 如果当前字符是大写字符，则变为小写字符之后，递归处理第 i + 1 个字符。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def dfs(self, s, path, i, ans):
        if i == len(s):
            ans.append(path)
            return

        self.dfs(s, path + s[i], i + 1, ans)
        if ord('a') <= ord(s[i]) <= ord('z'):
            self.dfs(s, path + s[i].upper(), i + 1, ans)
        elif ord('A') <= ord(s[i]) <= ord('Z'):
            self.dfs(s, path + s[i].lower(), i + 1, ans)

    def letterCasePermutation(self, s: str) -> List[str]:
        ans, path = [], ""
        self.dfs(s, path, 0, ans)
        return ans