LeetCode 784. 字母大小写全排列

Categories:

题目描述
思路分析
1. 解法一：回溯（推荐）
相似题目

题目描述

✅ 784. 字母大小写全排列

思路分析

解法一：回溯（推荐）

核心思路：

遇到字母时分两支：保持原样或切换大小写。

遇到数字直接加入路径继续。

深度优先生成所有组合。

复杂度分析：

时间复杂度：O(2^k)，其中 k 表示字母数量。

空间复杂度：O(k)，递归栈深度。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> res = new ArrayList<>();
        dfs(s.toCharArray(), 0, res);
        return res;
    }

    private void dfs(char[] chars, int index, List<String> res) {
        if (index == chars.length) {
            res.add(new String(chars));
            return;
        }

        if (Character.isLetter(chars[index])) {
            chars[index] = Character.toLowerCase(chars[index]);
            dfs(chars, index + 1, res);

            chars[index] = Character.toUpperCase(chars[index]);
            dfs(chars, index + 1, res);
        } else {
            dfs(chars, index + 1, res);
        }
    }
}

import "strings"

func letterCasePermutation(s string) []string {
	chars := []byte(s)
	res := make([]string, 0)

	var dfs func(idx int)
	dfs = func(idx int) {
		if idx == len(chars) {
			res = append(res, string(chars))
			return
		}

		if chars[idx] >= 'a' && chars[idx] <= 'z' || chars[idx] >= 'A' && chars[idx] <= 'Z' {
			chars[idx] = byte(strings.ToLower(string(chars[idx]))[0])
			dfs(idx + 1)
			chars[idx] = byte(strings.ToUpper(string(chars[idx]))[0])
			dfs(idx + 1)
		} else {
			dfs(idx + 1)
		}
	}

	dfs(0)
	return res
}

相似题目

题目	难度	考察点
17. 电话号码的字母组合	中等	回溯
78. 子集	中等	回溯
46. 全排列	中等	回溯
93. 复原 IP 地址	中等	回溯
77. 组合	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/92233202