发表于 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

• LC 题目链接