0784. 字母大小写全排列

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
本站总访问量  次  |  您是本站第  位访问者