Java 回溯算法解 LeetCode 784：字母大小写全排列的面试思路与代码详解

刚在云栈社区看到个帖子，挺有共鸣：公司裁了俩同事，一个月薪1万5，一个3万，他们的活儿全甩给了发帖的楼主。楼主顺嘴提了句“那是不是也该涨点薪”，结果被领导和同事说成是趁火打劫，搞得像犯了多大错一样，真是让人无语。

这事儿的核心，我觉得不在楼主提要求本身，而在公司的态度。活儿多了、责任重了，要求匹配的报酬，这是最基本的职场逻辑，不叫贪心，叫公平交易。不过话说回来，在那种情境下直接硬刚，确实容易被贴上“不识大体”的标签，这也是很多朋友不敢轻易开口的原因。

我的看法是，涨薪的诉求一点没错，但表达方式可以更职业化一些。比如，先把新接手的活儿干出个样子，拿出清晰的数据、成果，甚至梳理出其中的风险和额外付出，再去谈会更有底气。该争取的要争取，该拿的别怂，但前提是别因为一时冲动，反而砸了自己的饭碗。

那作为开发者，我们平时该怎么应对这种突增的“负载”呢？除了提升沟通技巧，更实在的是不断打磨自己的技术硬实力。比如，能把一些经典的算法面试题思路理得特别清楚，关键时刻就能派上用场。

面试题：字母大小写全排列

昨天晚上十一点多，我在公司楼下抽烟，手里还端着便利店的冰美式，苦得要命。我们组的小李突然微信上问我：“哥，那个字母大小写全排列，面试老爱考的，怎么写才能逻辑清晰不绕进去？”

我说，你这问题就跟线上系统的分支逻辑一样，控制不住，日志一多 debug 起来人就炸了，对吧？

这道题其实就一句话：给你一个字符串，里面可能有字母也可能有数字。字母你可以选择它的大写形式或小写形式，数字则保持不变。要求你把所有可能的组合都列出来。听起来像排列组合，但本质是“走到每个字符，看你要不要分叉”。只有字母才有分叉的权利（大小写两种选择），数字就一路直走。你别一上来就想什么奇技淫巧，先把“每一位要么选大写A要么选小写a”这个基本盘想清楚，代码框架就有了。

我当时还给小李扯了个生活化的例子：你晚上点个套餐，主菜可选辣或不辣（这就好比字母），饮料是固定的（好比数字）。你从第一项开始选，遇到主菜就分出“辣”和“不辣”两条路，遇到饮料就继续沿着当前的路走。嗯，说着说着我烟都快烧到手了。

代码实现上，我一般直接用回溯（DFS），不整太多花活，写出来也方便跟面试官解释。下面这个是 Java 版本的，你可以直接贴到 LeetCode 784 题里跑：

import java.util.*;

public class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null) return ans;

        char[] arr = s.toCharArray();
        dfs(arr, 0, ans);
        return ans;
    }

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

        char c = arr[idx];

        // 数字或其它符号：不分叉，直接进入下一层
        if (!Character.isLetter(c)) {
            dfs(arr, idx + 1, ans);
            return;
        }

        // 分叉1：转为小写
        arr[idx] = Character.toLowerCase(c);
        dfs(arr, idx + 1, ans);

        // 分叉2：转为大写
        arr[idx] = Character.toUpperCase(c);
        dfs(arr, idx + 1, ans);

        // 这里其实不需要显式“还原”arr[idx]，因为每次递归调用都会覆盖它
        // 但如果你心里不踏实，最后加一句 arr[idx] = c; 也没问题
    }

    // 如果你想在本地跑一下，可以启用这个main方法
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.letterCasePermutation("a1b2"));
        // 可能的输出: [a1b2, a1B2, A1b2, A1B2]
    }
}

小李看完代码又问：“那这个时间复杂度是不是会爆炸？”我说你别慌，咱们来分析一下。假设字符串里有 k 个字母，那么最终的结果组合数就是 2^k 个。你再怎么优化，也得把所有结果都生成出来，总不能把答案藏起来不给面试官看，对吧？所以时间复杂度是 O(2^k * n)，这里的 n 是字符串长度（因为最后构造每个答案字符串需要 O(n) 时间）。空间复杂度主要是递归调用栈的深度 O(n)，再加上存储结果集合的空间。

还有个细节我顺手提醒了他：在这个解法里，我们直接操作 char[] 数组进行原地修改，这比用 StringBuilder 不断 new 新对象要更稳妥一些。尤其是在 Java 里，如果你在递归中疯狂拼接字符串，很容易无意间引发频繁的 GC，给你表演个“程序卡顿几秒钟”。当然，这题的数据规模通常不会太大，但代码写得清晰、效率意识强，总是加分项。

最后，如果面试官问你“为什么不用全排列的框架？”，你就可以清楚地告诉他：我们只对字母位做“二选一”的分支，数字位不参与分支选择，这样逻辑更贴合题意，也避免了不必要的计算。

反正我俩聊到最后，楼下保安都来催我回去，说晚上风大别在外面晃悠。我一边收拾电脑一边还在想代码的边界条件……哦对了，明天早上还有个需求评审会，不多说了，真是困死了。

职场上的糟心事或许无法立刻解决，但至少我们可以把技术问题梳理清楚。如果你在刷题或工作中遇到其他有意思的问题，欢迎来社区一起聊聊。保持思考，持续学习，这才是咱们开发者最硬的底气。