LeetCode每日一题——784. 字母大小写全排列

LeetCode每日一题系列

题目：784. 字母大小写全排列
难度：普通

---

---

题目

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

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例

示例 1：

输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

示例 2:

输入: s = “3z4”
输出: [“3z4”,“3Z4”]

提示:

1 <= s.length <= 12
s 由小写英文字母、大写英文字母和数字组成

思路

递归+回溯+set去重
使用递归和回溯可以获得所有可能的结果，然后再利用集合的属性去重即可，这里需注意：只需要对字母进行操作，遇到数字直接跳过。详情看下方题解。

题解

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
    	# 去重
        ans = set()
        s = list(s)
        n = len(s)
        # 递归函数
        def process(s, index):
        	# 每一次调用都加上可能的结果
            ans.add(''.join(s))
            # 从前往后遍历，修改字母元素
            for i in range(index, n):
            # 判断是否字母
             if s[i].isalpha():
                tmp = s[i]
                # 转换大小写
                if s[i].isupper():
                    s[i] = s[i].lower()
                    # 按顺序递归调用
                    process(s, i + 1)
                    s[i] = tmp
                else:
                    s[i] = s[i].upper()
                    # 按顺序递归调用
                    process(s, i + 1)
                    s[i] = tmp  
        process(s, 0)
        return list(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28