力扣-784. 字母大小写全排列 & 全排列

题目描述

思路和实现

784. 字母大小写全排列

广度优先搜索

提到广度优先搜索，我们就要想到队列，所以我们会使用一个队列来保存每一字符串。怎么进行广度优先搜索呢？当然是一直搜下去直到队列为空啦，
在搜索的过程中，我们每次取队列头的字符串，首先看看当前字符串长度是否和给我们的字符串s的长度一致，是的话塞到结果列表里，
不是的话，就看在它后面的那个字符串是字母还是数字，如果是字母，就把它的大小写都加到当前字符串里，然后塞队尾里；如果是数字，那就直接加到当前字符串里，然后塞队尾。

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        q = deque()
        q.append("")
        result = []
        s_len = len(s)
        while q:
            tmp_str = q.popleft()
            n = len(tmp_str)
            if n == s_len:
                result.append(tmp_str)
            else:
                if s[n].isalpha():  # 当前字符串后面一位是字母
                    q.append(tmp_str + s[n])
                    q.append(tmp_str + s[n].swapcase())
                else:  # 是数字
                    q.append(tmp_str + s[n])
        return result

深度优先搜索

既然都有广度优先搜索，那自然也有深度优先搜索啦，那深度优先搜索自然也就是使用栈来保存每一字符串啦，剩下的思路其实是和上面广度所述差不多的，
不过深度优先搜索可以使用递归，也可以不使用，这里两种都写一下吧。
先给出不使用递归的版本

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        q = deque()
        q.append("")
        result = []
        s_len = len(s)
        while q:
            tmp_str = q.pop()
            n = len(tmp_str)
            if n == s_len:
                result.append(tmp_str)
            else:
                if s[n].isalpha():  # 当前字符串后面一位是字母
                    q.append(tmp_str + s[n].swapcase())
                    q.append(tmp_str + s[n])
                else:  # 是数字
                    q.append(tmp_str + s[n])
        return result

可以看到代码基本是没变的，只是把队列换成了栈（因为懒所以没有改变量名称，用的还是q(queue)而不是s(stack)），顺便为了保证输出顺序，先压入转换大小写后的字符串，再压当前字符串。
使用递归的话，我们可以不使用额外空间存放字符串，直接使用字符串转为列表，然后进行深度优先搜索。如果遇到数字，就跳过；如果长度够了，就把当前列表转回字符串并加入结果集中；如果是字母，就调用递归，然后转换大小写再次递归，两次递归结束后别忘记回溯，即再次把大小写转换回去。
下面是使用递归版本

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        result = []
        s_len = len(s)

        def dfs(cur_s, cur_len):
            while cur_len < s_len and s[cur_len].isdigit():
                cur_len += 1
            if cur_len == s_len:  # 递归出口
                result.append(''.join(cur_s))
                return
            dfs(cur_s, cur_len + 1)
            cur_s[cur_len] = cur_s[cur_len].swapcase()  # 改变大小写再次搜索
            dfs(cur_s, cur_len + 1)
            cur_s[cur_len] = cur_s[cur_len].swapcase()  # 回溯

        dfs(list(s), 0)
        return result

46. 全排序

深度优先搜索

对于这种全排列，可以画一颗树来方便理解，然后再由此联想到dfs——深度优先搜索来做。

既然有递归，那首先想到的就是递归出口，这个递归出口怎么设置呢？根据树图可以联想到利用深度和题目所给数组长度：if depth == length: return，同时也能知道此时找到了一个排列，可以将其加入结果中。
然后要想的就是怎么进行递归了。图很直观地告诉我们，每一深度都遍历一遍数组，那就照做。不过还存在一个问题，在下一层中，我们不能使用已经用过的数，也就是说，在深度搜索的时候，还需要记得用过哪些数了。
关于这点，可以使用一个辅助数组来帮助记忆，建立一个flag数组，下标对应nums数组每个数，使用visited和unvisited两个值表示使用过和未使用过。
但是还没有结束，因为在完成一次搜索（递归）后还需要进行回溯，才能保证能继续进行搜索并搜索完。也就是说，在一次递归完成后（depth == length），我们需要把使用过的值再次标记为未使用，这叫回溯。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        tmp = []
        length = len(nums)
        if length == 0:
            return result
        flag = ["unvisited"] * length  # 为方便理解，这里用字符串来代替布尔值，也可使用布尔值（会更快）
        def dfs(depth: int) -> None:
            if depth == length:
                result.append(tmp[:])  # 记住是拷贝一份tmp的列表，而不是加入tmp的引用指向的列表
                return
            for i in range(length):
                if flag[i] == "unvisited":
                    flag[i] = "visited"
                    tmp.append(nums[i])
                    dfs(depth + 1)  # 进行深度优先搜索
                    flag[i] = "unvisited"  # 搜索完后，需要回溯，即把当前节点标记成未未访问的
                    tmp.pop()  # 回溯第二步，因为变成未访问了，所以也要把这个数弹出
        dfs(0)
        return result

47. 全排列 II（包含重复数字的排列）

深度优先搜索

在这一题中，题目所给出的nums数组中会包含重复的数字，但是输出不能包含重复的排列，所以这一题的大体思路其实是和上一题一样的，
而重点就是：如何去重
我们先来看这颗树，可以发现，只要把同一层的重复的数跳过就行了，很简单对吧！

对个鬼啊，深度优先搜索你怎么保留同一层的状态啊，同一层找这不广度优先搜索吗？
好吧，我没思路了，所以我们先尝试暴力搜索。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        tmp = []
        length = len(nums)
        if length == 0:
            return result
        flag = ["unvisited"] * length  # 为方便理解，这里用字符串来代替布尔值，也可使用布尔值（会更快）
        def dfs(depth: int) -> None:
            if depth == length and tmp not in result:
                result.append(tmp[:])  # 记住是拷贝一份tmp的列表，而不是加入tmp的引用指向的列表
                return
            for i in range(length):
                if flag[i] == "unvisited":
                    flag[i] = "visited"
                    tmp.append(nums[i])
                    dfs(depth + 1)  # 进行深度优先搜索
                    flag[i] = "unvisited"  # 搜索完后，需要回溯，即把当前节点标记成未未访问的
                    tmp.pop()  # 回溯第二步，因为变成未访问了，所以也要把这个数弹出
        dfs(0)
        return result

虽然但是AC了，那这就是可行的思路，所以什么题都要先尝试暴力嘛（
ok，接下来是看别人题解时间！整理了一下思路放下边这张图了。（原来是叫剪枝操作啊

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        tmp = []
        length = len(nums)
        nums.sort()
        if length == 0:
            return result
        flag = ["unvisited"] * length  # 为方便理解，这里用字符串来代替布尔值，也可使用布尔值（会更快）
        def dfs(depth: int) -> None:
            if depth == length:
                result.append(tmp[:])  # 记住是拷贝一份tmp的列表，而不是加入tmp的引用指向的列表
                return
            for i in range(length):
                if flag[i] == "unvisited":
                    if i >= 1 and nums[i - 1] == nums[i] and flag[i - 1] == "unvisited":
                        continue
                    flag[i] = "visited"
                    tmp.append(nums[i])
                    dfs(depth + 1)  # 进行深度优先搜索
                    flag[i] = "unvisited"  # 搜索完后，需要回溯，即把当前节点标记成未未访问的
                    tmp.pop()  # 回溯第二步，因为变成未访问了，所以也要把这个数弹出

        dfs(0)
        return result

---

希望本文章能够帮到您~