企业官网建设流程全解析

FindCaseCombinations回溯法入门：如何生成字符串2^n种大小写组合

【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb

想搞懂回溯法和组合枚举吗？在 AirBnB 面试题库（airbnb 项目）的第 20 题Find Case Combinations of a String（字符串大小写组合）中，你需要为一个字符串生成全部的2^n种大小写组合——比如 "ab" 可以变成 "ab"、"Ab"、"aB"、"AB" 共 4 种。下面这篇入门教程带你从零理解这道经典题目的数学原理、位运算枚举技巧，以及一份可运行的 Java 参考实现。

🧩 题目描述：为什么是 2^n 种组合？

题目的原文要求是：找出一个字符串所有小写/大写的组合。例如 "ab" 的输出为 "ab"、"Ab"、"aB"、"AB"，也就是2^n（n 为字符个数）个结果字符串。目标是逐个测试这些字符串，看它是否匹配一个隐藏字符串（hidden string）。

为什么恰好是2^n？

每个字母都独立地面临"大写还是小写"这个二选一，根据乘法原理，n 个字母的总组合数就是 2 × 2 × … × 2 =2^n。这正是回溯法中最典型的"每一层做二选一决策"的场景。

🧠 两种思路：回溯 vs 位掩码枚举

思路一：递归回溯（经典思路）

回溯法的核心模式可以概括为三步：

1. 选择：对当前位的字母，先尝试小写，再尝试大写
2. 递归：处理完当前位后，递归处理下一位
3. 撤销（回溯）：回退时恢复字母状态，保证不影响其他分支

决策树长这样（以 "ab" 为例）：

"" / \ a A / \ / \ ab aB Ab AB

每个叶子节点就是一个完整组合，遍历整棵二叉树恰好得到 2^n 个结果。这种"逐位决策 + 回退"的模式，是学习回溯法的最好入口。

思路二：位掩码枚举（airbnb 项目采用）

airbnb 项目给出的官方解法非常巧妙——用一个整数的二进制位来表示每一种组合：

• 整数i从 0 数到 2^n − 1，每一个i代表一种组合
• 第j位为 1 → 第 j 个字母用大写；为 0 → 用下写
• 例如 "ab" 中，i=1（二进制 01）→ "Ab"，i=2（10）→ "aB"，i=3（11）→ "AB"

这种位运算技巧把递归树"压平"成了两层循环，代码更短、无递归开销，是面试中非常加分的写法。

🔍 源码解析：strComb 是如何工作的？

参考实现位于 src/main/java/find_case_combinations_of_a_string/FindCaseCombinationsofaString.java，核心方法只有十来行：

public List<String> strComb(String text) { List<String> res = new ArrayList<>(); char[] chars = text.toCharArray(); for (int i = 0, n = (int) Math.pow(2, chars.length); i < n; i++) { char[] curr = new char[chars.length]; for (int j = 0; j < chars.length; j++) { curr[j] = (isBitSet(i, j)) ? Character.toUpperCase(chars[j]) : Character.toLowerCase(chars[j]); } res.add(new String(curr)); } return res; }

逐行理解：

• 外层循环i遍历 0 到 2^n−1，即遍历每一种"大小写方案"
• isBitSet(i, j)是关键的小工具方法：(n >> offset & 1) != 0，即把i右移 j 位后看最低位，判断第 j 位是否为 1
• 内层循环j逐位决策：位为 1 转大写，为 0 转小写
• 拼好一个字符串就加入结果集

以 "AirBnB" 为例，程序将生成 64 个组合：i=0输出 "airbnb"，i=1输出 "Airbnb"，i=62输出 "aIRBNB"，i=63输出 "AIRBNB"——与单元测试的断言完全一致（见同文件中的 UnitTest.test1）。

⚙️ 本地运行：一键跑通单元测试

这个题库基于 Gradle 构建，只需两步即可运行本题的测试：

1. 克隆仓库

   git clone https://gitcode.com/gh_mirrors/ai/airbnb

2. 进入项目目录后，运行本题的单测（要求 Java ≥ 11.106、Gradle ≥ 5.6.3）：

   gradle -Dtest.single=FindCaseCombinationsofaString test

测试会验证 4 个关键断言：组合总数为 64，且首、次、倒数第二、末尾四个组合的值正确，帮助你快速确认枚举顺序是否符合"二进制递增"的规律。

📊 复杂度分析

需要清醒认识到：2^n 是指数级增长。n = 20 时组合数约 100 万，n = 30 时约 10 亿——这就是为什么题目设定为"生成后逐个匹配隐藏串"时，实际场景通常会配合剪枝（如逐位前缀过滤）或改用正则匹配(?i)airbnb这类思路来避免全量枚举。

💡 举一反三：这道题教会你的 3 件事

1. 回溯法的通用框架：逐位决策 → 递归深入 → 回溯撤销，这套模式可直接迁移到子集生成、全排列、N 皇后等经典题目
2. 位运算枚举组合：用整数二进制位编码"选/不选"决策，是枚举子集类问题的利器，比递归更省栈空间
3. 先算数量再动手：遇到"生成所有组合"类题目，先问自己总共有多少结果（2^n？n!？），能立刻判断算法是否可行

完成本题后，建议顺藤摸瓜挑战题库中的相邻题目：Menu Combination Sum（菜单组合求和） 和 K Edit Distance（K 编辑距离），把"组合枚举 + 匹配过滤"的套路彻底练熟。

【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb