跳至主要內容

0784. 字母大小写全排列

ITCharge大约 2 分钟

0784. 字母大小写全排列open in new window

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

题目链接

题目大意

描述:给定一个字符串 ss,通过将字符串 ss 中的每个字母转变大小写,我们可以获得一个新的字符串。

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

说明

  • 答案可以以任意顺序返回输出。
  • 1s.length121 \le s.length \le 12
  • ss 由小写英文字母、大写英文字母和数字组成。

示例

  • 示例 1:
输入:s = "a1b2"
输出:["a1b2", "a1B2", "A1b2", "A1B2"]
  • 示例 2:
输入: s = "3z4"
输出: ["3z4","3Z4"]

解题思路

思路 1:回溯算法

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

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度n×2nn \times 2^n,其中 nn 为字符串的长度。
  • 空间复杂度O(1)O(1),除返回值外不需要额外的空间。