题目

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

  1. 示例:
  2. 输入: S = "a1b2"
  3. 输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
  4. 输入: S = "3z4"
  5. 输出: ["3z4", "3Z4"]
  6. 输入: S = "12345"
  7. 输出: ["12345"]

注意：

  • S 的长度不超过12。
  • S 仅由数字和字母组成。

答案

class Solution:
    def letterCasePermutation(self, S: str) -> List[List[str]]:
        res = []

        def helper(S, index):
            if index == len(S):
                res.append(S)
                return
            helper(S, index + 1)
            if ord(S[index]) >= 65:
                l = list(S)[:]
                l[index] = chr(ord(S[index]) ^ 32)
                S = ''.join(l)
                helper(S, index + 1)

        helper(S, 0)

        return res

Note

dfs回溯

  1. 一步到底到字符串最后

    image.png

  2. 当前index与字符串长度相等，答案中追加这一条，

  3. 回溯到b，不是数字，转换大小写^32 ,再向下进行递归
  4. 走完里边的递归再回到当前向上走到1，再到a时不是数字再进行递归

python不能直接修改字符串中的字符，先list()转换为一个列表再修改，
字母不能直接与数字异或，先用ord转化为ascii再和32异或

例如 ‘a’ ascii是 97 二进制是 110001 32 二进制是 10000 97^32 = 100001 = 65 = ‘A’