# 第78期-基础算法：回溯字母大小写全排列

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

# 1 问题描述

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例 1:

输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2:

输入: S = "3z4"
输出: ["3z4", "3Z4"]

示例 3:

输入: S = "12345"
输出: ["12345"]

初始代码

from typing import List
class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        #在此之间填写代码

print(Solution().letterCasePermutation("a1b2"))
print(Solution().letterCasePermutation("3z4"))
print(Solution().letterCasePermutation("12345"))

1
2
3
4
5
6
7
8

# 2 解题思路

标签：回溯
从左往右依次遍历字符，过程中保持 res 为已遍历过字符的字母大小全排列。
例如，当 S = "abc" 时，考虑字母 "a", "b", "c"，初始令 res = [""]，依次更新 res = ["a", "A"]， res = ["ab", "Ab", "aB", "AB"]， res = ["abc", "Abc", "aBc", "ABc", "abC", "AbC", "aBC", "ABC"]。

# 3 解题方法

from typing import List
class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        cur=[s.lower()]
        a=len(s)
        def backtrack(s,m):
            for i in range(m,a):
                if s[i] not in ['1','2','3','4','5','6','7','8','9','0']:
                    cur.append(s[:i]+s[i].upper()+s[i+1:])
                    backtrack(s[:i]+s[i].upper()+s[i+1:],i+1)
            return cur
        return backtrack(s.lower(),0)

print(Solution().letterCasePermutation("a1b2"))
print(Solution().letterCasePermutation("3z4"))
print(Solution().letterCasePermutation("12345"))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第1-3，14-16行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义列表cur并在其内添加元素s的全小写形态
第5行： 定义变量a并赋值字符串s的长度
第6行： 创建backtrack回溯函数，内部变量为字符串s和初始遍历点m
第7行： 使用for循环遍历从m到a的值并赋值给i，用于遍历字符串s
第8行： 判断字符串中索引i对应的元素是否不是数字
第9行： 若不是数字，则将该元素变为大写并将字符串添加至列表中
第10行： 对后面还未遍历到的字符串进行同样的操作
第11行： 运行完毕后返回所有可能形成的列表cur
第12行： 使用backtrack函数，返回所有可能

代码运行结果为：

# 算法讲解

这里用到了基础算法：回溯，简单讲解下这个算法：
回溯
回溯是很经典的一个算法，什么是回溯，回溯其实是一种暴力枚举的方式，为啥都暴力了还是很经典的一种方法呢，其实是因为有些问题我们能暴力出来就不错了，就别要其他自行车了。常见的回溯类问题：组合；排列；切割；子集；棋牌；
其实回溯算法就是常说的DFS,本质上是一种暴力枚举算法；
回溯算法常用于解决的问题：
组合
排列
切割
子集
棋盘：N皇后

比如最经典的排列。从1,2,3,4,5中取3个数组成排列有多少种，我们肯定会解决这种问题，但是程序怎么写呢。想一下我们解决这个问题的过程，我们先选1，然后第二个数可以选2，第三个数可以选3，这是一种答案了，然后呢，换第三个数，第三个数选4，又一种答案，再换，第三个数选5，没得选了，所以以12打头的数都选完了，得到三种答案.然后再换第二个数，第二个数选3，然后第三个数选4，注意是组合问题所以我们不能退往回选2了，不然就重复了。就是这样一种选择方案，一直到第3个数选成了3，得到答案345，就不用往后进行了。

# 4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码
AI大学堂公众号.png