LeetCode刷题--- 字母大小写全排列

个人主页：元清加油_【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. 不进?处理；
2. 若当前字?是英?字?并且是?写，将其修改为?写；
3. 若当前字?是英?字?并且是?写，将其修改为?写。

一、画出决策树

决策树就是我们后面设计函数的思路

---

二、设计代码

（1）全局变量

   string path;
   vector<string> ret;

• ret（存储转变大小写，获得一个个新的字符串）
• path（组合的路径记录）

（2）设计递归函数

void dfs(string s, int pos);  // 表示现在要处理的元素的下标

• 参数：s（字符串），pos（当前要处理的元素下标）；
• 返回值：无；
• 函数作用：查找所有可能的字符串集合，并将其记录在答案列表。；

1. 递归结束条件：当前需要处理的元素下标越界，表?处理完毕，记录当前状态并返回；
2. 判断当前元素是否为数字，若是，对当前元素不进?任何处理，直接递归下?位元素；
3. 判断当前元素是否为?写字?，若是，将其修改为?写字?并递归下?个元素，递归结束时撤销修改操作；
4. 判断当前元素是否为?写字?，若是，将其修改为?写字?并递归下?个元素，递归结束时撤销修改操作；

以上思路讲解完毕，大家可以自己做一下了

---

代码实现

• 时间复杂度：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;
    }
};