个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
http://t.csdnimg.cn/yUl2I
【C++】
http://t.csdnimg.cn/6AbpV
数据结构与算法
http://t.csdnimg.cn/hKh2l
前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分:
1、题目解析
2、算法原理思路讲解
3、代码实现
字母大小写全排列
题目链接:字母大小写全排列
题目
给定一个字符串 s
,通过将字符串 s
中的每个字母转变大小写,我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例 1:
输入:s = "a1b2" 输出:["a1b2", "a1B2", "A1b2", "A1B2"]
示例 2:
输入: s = "3z4" 输出: ["3z4","3Z4"]
提示:
1 <= s.length <= 12
s
由小写英文字母、大写英文字母和数字组成
解法
题目解析
- 题目的意思非常简单,给定一个字符串
s
- 通过将字符串
s
中的每个字母转变大小写,我们可以获得一个新的字符串。 - 返回 所有可能得到的字符串集合 ,以 任意顺序 返回输出。
示例 1:
输入:s = "a1b2" 输出:["a1b2", "a1B2", "A1b2", "A1B2"]
算法原理思路讲解
只需要对英⽂字⺟进⾏处理,处理每个元素时存在三种情况
- 不进⾏处理;
- 若当前字⺟是英⽂字⺟并且是⼤写,将其修改为⼩写;
- 若当前字⺟是英⽂字⺟并且是⼩写,将其修改为⼤写。
一、画出决策树
决策树就是我们后面设计函数的思路
二、设计代码
(1)全局变量
string path;vector<string> ret;
- ret(存储转变大小写,获得一个个新的字符串)
- path(组合的路径记录)
(2)设计递归函数
void dfs(string s, int pos); // 表示现在要处理的元素的下标
- 参数:s(字符串),pos(当前要处理的元素下标);
- 返回值:无;
- 函数作用:查找所有可能的字符串集合,并将其记录在答案列表。;
从前往后按序进⾏递归,递归流程如下
- 递归结束条件:当前需要处理的元素下标越界,表⽰处理完毕,记录当前状态并返回;
- 判断当前元素是否为数字,若是,对当前元素不进⾏任何处理,直接递归下⼀位元素;
- 判断当前元素是否为⼩写字⺟,若是,将其修改为⼤写字⺟并递归下⼀个元素,递归结束时撤销修改操作;
- 判断当前元素是否为⼤写字⺟,若是,将其修改为⼩写字⺟并递归下⼀个元素,递归结束时撤销修改操作;
以上思路讲解完毕,大家可以自己做一下了
代码实现
- 时间复杂度:O(n×),其中 n 表示字符串的长度。递归深度最多为 n,所有可能的递归子状态最多为 个,每次个子状态的搜索时间为 O(n),因此时间复杂度为 O(n×)。
- 空间复杂度:O(n×)。递归深度最多为 n,。队列中的元素数目最多为 个,每次个子状态的搜索时间为 O(n),因此空间复杂度为 O(n×) 。
class Solution {
public:string path;vector<string> ret;void dfs(string s, int pos) // 表示现在要处理的元素的下标{if (path.size() == s.size()){ret.push_back(path);return;}if (s[pos] >= '0' && s[pos] <= '9'){path.push_back(s[pos]);dfs(s, pos + 1);path.pop_back();}else{if (s[pos] >= 'a' && s[pos] <= 'z'){path.push_back(s[pos]);dfs(s, pos + 1);path.pop_back();path.push_back(s[pos]-32);dfs(s, pos + 1);path.pop_back();}else{path.push_back(s[pos]);dfs(s, pos + 1);path.pop_back();path.push_back(s[pos] + 32);dfs(s, pos + 1);path.pop_back();}}}vector<string> letterCasePermutation(string s) {dfs(s, 0);return ret;}
};