大型门户网站,嘉兴做网站设计,idc机房,网站开发与网页设计大作业个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】 http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言#xff1a;这个专栏主要讲述递归递归、搜索与回…个人主页元清加油_【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 12s 由小写英文字母、大写英文字母和数字组成 解法
题目解析
题目的意思非常简单给定一个字符串 s 通过将字符串 s 中的每个字母转变大小写我们可以获得一个新的字符串。返回 所有可能得到的字符串集合 以 任意顺序 返回输出。
示例 1
输入s a1b2
输出[a1b2, a1B2, A1b2, A1B2] 算法原理思路讲解 只需要对英⽂字⺟进⾏处理处理每个元素时存在三种情况 不进⾏处理 若当前字⺟是英⽂字⺟并且是⼤写将其修改为⼩写 若当前字⺟是英⽂字⺟并且是⼩写将其修改为⼤写。
一、画出决策树 决策树就是我们后面设计函数的思路 二、设计代码
1全局变量 string path;vectorstring 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;vectorstring 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();}}}vectorstring letterCasePermutation(string s) {dfs(s, 0);return ret;}
};
