本文讲述了python基础编程100例：第78期-基础算法：回溯 字母大小写全排列！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

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

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"))

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-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，就不用往后进行了。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。