题目
难度：★★☆☆☆
类型：字符串
给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
注意
S 的长度不超过12。
S 仅由数字和字母组成。
示例
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
输入: S = "3z4"
输出: ["3z4", "3Z4"]
输入: S = "12345"
输出: ["12345"]
解答
方案1：回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。（来自百度百科）。
在这道题中，回溯法从左到右扫描字符串，当遇到字母时考虑使用该字母的大写和小写形式两种可能，直到遍历到字符串最后一个字符。
这里我们定义函数dfs(start, tmp)实现回溯，函数的输入有两个：start是遍历到的当前位，tmp是遍历到当前位时已经记录的前半部分子串。回溯的过程：针对当前位S[start]（该字符赋给了变量c）的不同进行不同操作：
-
首先判断当前是否到达回溯终点，这里根据tmp的长度是否恰好为输入字符串S的长度判断；
-
如果没有到达回溯终点，则判断该字符c的类型：
（1）如果是数字，则直接进行下一轮回溯：dfs(start+1, tmp+c)；
（2）如果是大写字母，则考虑使用它本身以及使用它的小写形式两种情况：dfs(start+1, tmp+c)和dfs(start+1, start+c.lower())；
（3）如果是小写字母，则考虑使用它本身以及使用它的大写形式两种请款：dfs(start+1, tmp+c)和dfs(start+1, start+c.upper())。
这里注意输入为空的处理。
class Solution(object):
def letterCasePermutation(self, S):
res = []
if not S:
return [""]
def dfs(start, tmp):
if len(tmp) == len(S): # 已经找到了一个答案
res.append(tmp)
return
c = S[start]
# print start, temp
if c.isdigit(): # 数字就直接加
dfs(start + 1, tmp + c)
elif S[start].islower():
# 字母就加本身和对立面
dfs(start + 1, tmp + c)
dfs(start + 1, tmp + c.upper())
else:
dfs(start + 1, tmp + c)
dfs(start + 1, tmp + c.lower())
dfs(0, "")
return res
有些逻辑可以合并：
class Solution(object):
def letterCasePermutation(self, S):
if not S:
return [""]
res = []
def dfs(start, temp):
if len(temp) == len(S): # 已经找到了一个答案
res.append(temp)
return
c = S[start]
dfs(start + 1, temp + c)
if not c.isdigit():
c = c.upper() if c.islower() else c.lower()
dfs(start + 1, temp + c)
dfs(0, "")
return res
方案2：线性扫描
我们可以直接使用线性方式进行扫描，每次扫描从结果列表中取出临时子串，并根据当前字符的情况在临时子串后添加字符：
（1）如果当前字符是数字：直接添加；
（2）如果当前字符是大写字母：除添加本身外，还要添加小写形式；
（3）如果当前字符是小写字母：除添加本身外，还要添加大写形式。
每次用新的结果列表更新原列表。
class Solution(object):
def letterCasePermutation(self, S):
res = [""]
for c in S:
next_res = []
for tmp in res:
next_res.append(tmp+c)
if not c.isdigit():
c = c.upper() if c.islower() else c.lower()
next_res.append(tmp + c)
res = next_res
return res
如有疑问或建议，欢迎评论区留言~
网友评论