LeetCode_回溯_BFS_中等_784.字母大小写全排列

╰+攻爆jí腚メ 2023-10-07 20:51 31阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

**示例 1：**  
输入：s = “a1b2”  
输出：\[“a1b2”, “a1B2”, “A1b2”, “A1B2”\]

**示例 2：**  
输入: s = “3z4”  
输出: \[“3z4”,“3Z4”\]

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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/letter-case-permutation

## 2.思路 ##

（1）回溯算法

（2）BFS

思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_回溯\_中等\_46.全排列][LeetCode_46.]

## 3.代码实现（Java） ##

//思路1————回溯算法
    class Solution {
        
        
        // res 用于保存最终的结果
        List<String> res = new ArrayList<>();
        
        public List<String> letterCasePermutation(String s) {
        
            char[] chs = s.toCharArray();
            backtrace(chs, 0);
            return res;
        }
            
        public void backtrace(char[] chs, int index) {
        
            // 找到 chs[index...chs.length - 1] 中的第一个字母
            while (index < chs.length && Character.isDigit(chs[index])) {
        
                index++;
            }
            if (index == chs.length) {
        
                res.add(new String(chs));
                return;
            }
            chs[index] ^= 32;
            backtrace(chs, index + 1);
            chs[index] ^= 32;
            backtrace(chs, index + 1);
        }
    }

//思路2————BFS
    class Solution {
        
        public List<String> letterCasePermutation(String s) {
        
            // res 用于保存最终的结果
            List<String> res = new ArrayList<>();
            Queue<StringBuilder> queue = new ArrayDeque<>();
            queue.offer(new StringBuilder());
            int length = s.length();
            while (!queue.isEmpty()) {
        
                StringBuilder builder = queue.peek();
                if (builder.length() == length) {
        
                    res.add(builder.toString());
                    queue.poll();
                } else {
        
                    int index = builder.length();
                    if (Character.isLetter(s.charAt(index))) {
        
                        StringBuilder next = new StringBuilder(builder);
                        next.append((char) (s.charAt(index) ^ 32));
                        queue.offer(next);
                    }
                    builder.append(s.charAt(index));
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/letter-case-permutation/solution/zi-mu-da-xiao-xie-quan-pai-lie-by-leetco-cwpx/
[LeetCode_46.]: https://blog.csdn.net/weixin_43004044/article/details/119631772