JZX轻语：简
LeetCode 784 - 字母大小写全排列
发表于2024年05月05日
一般这种全排列题目都可用回溯法解决，在每次递归中，如果遇到数字则直接处理下一个字符；否则，如果是字符则额外进行大小写转换后再处理一次。为减少递归次数，可以在一次递归中直接跳过数字。
原做法：
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
ans = []
def traceback(cur: List[str]):
nonlocal s
if len(cur) == len(s):
ans.append(''.join(cur))
return
pos = len(cur)
s_pos_ord = ord(s[pos])
if ord('a') <= s_pos_ord <= ord('z'):
cur.append(chr(s_pos_ord - ord('a') + ord('A')))
traceback(cur)
cur.pop()
elif ord('A') <= s_pos_ord <= ord('Z'):
cur.append(chr(s_pos_ord - ord('A') + ord('a')))
traceback(cur)
cur.pop()
cur.append(s[pos])
traceback(cur)
cur.pop()
traceback([])
return ans看了官方答案后，在一次递归中跳过数字，遇到字母时使用Python原生的swapcase进行转换：
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
ans = []
def traceback(s_chars: List[str], pos: int):
nonlocal s
# 数字的直接在本次递归中跳过
while pos < len(s_chars) and s_chars[pos].isdigit():
pos += 1
# 找到一个结果
if pos == len(s_chars):
ans.append(''.join(s_chars))
return
# 使用原字母遍历一次
traceback(s_chars, pos + 1)
s_chars[pos] = s_chars[pos].swapcase()
# 翻转后再遍历一次
traceback(s_chars, pos + 1)
# 恢复现场
s_chars[pos] = s_chars[pos].swapcase()
traceback(list(s), 0)
return ans