[数据结构与算法]【Leetcode每日一题.784:字母大小写全排列~~~DFS深度优先遍历(递归+回溯)+BFS广度优先遍历】

题目描述

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1：

输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]
示例 2:

输入: s = “3z4”
输出: [“3z4”,“3Z4”]

提示:

1 <= s.length <= 12
s 由小写英文字母、大写英文字母和数字组成

解题思路

1. 这道题目可以通过DFS或者BFS来解决。
2. DFS思路:通俗来说也就是递归的设计思路。

首先就是循环结束的条件:如果当我们来到字符串的结尾，将结果添加到最后的结果中。
接下来就是中间的过程:当我们遇到是数字的时候就直接跳过，接下来就是大小写字母，每个字母有俩个选择，一个是大写，另外一个就是小写，因为大小写字母差值为32，所以说我们可以通过^32来表示求值。

3. BFS思路:通过队列来辅助实现:

如果队列中当前序列的长度等于 s 的长度，则表示当前序列已经搜索完成，该序列为全排列中的一个合法序列；
如果当前位置为一个数字，则队列中所有的序列的末尾均加上当前数字，将修改后的序列再次进入到队列中；
如果当前位置为一个字母，此时我们在上述序列的末尾依次分别加上当前位置的小写形式 和大写形式，再次将上述数列放入队列；

实现代码

深度优先遍历

class Solution {
    public List<String> letterCasePermutation(String s) {
        char[] c=s.toCharArray();
        List<String> res=new ArrayList<>();
        process(c,0,res);
        return res;
    }

    public void process(char[] c,int index,List<String> res){
        while(index<c.length&&Character.isDigit(c[index])){
            index++;
        }
        if(index==c.length){
            res.add(new String(c));
            return;
        }
        c[index]^=32;
        process(c,index+1,res);
        c[index]^=32;
        process(c,index+1,res);
    }
}

广度优先遍历

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> ans = new ArrayList<String>();
        Queue<StringBuilder> queue = new ArrayDeque<StringBuilder>();
        queue.offer(new StringBuilder());
        while (!queue.isEmpty()) {
            StringBuilder curr = queue.peek();
            if (curr.length() == s.length()) {
                ans.add(curr.toString());
                queue.poll();
            } else {
                int pos = curr.length();
                if (Character.isLetter(s.charAt(pos))) {
                    StringBuilder next = new StringBuilder(curr);
                    next.append((char) (s.charAt(pos) ^ 32));
                    queue.offer(next);
                }
                curr.append(s.charAt(pos));
            }
        }
        return ans;
    }
}

运行结果