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^nn 为字符个数个结果字符串。目标是逐个测试这些字符串看它是否匹配一个隐藏字符串hidden string。为什么恰好是2^n字符串长度 n每个字母的选择总组合数1如 a小写 / 大写2 种2^1 22如 ab每位各 2 种2^2 46如 AirBnB每位各 2 种2^6 64每个字母都独立地面临大写还是小写这个二选一根据乘法原理n 个字母的总组合数就是 2 × 2 × … × 2 2^n。这正是回溯法中最典型的每一层做二选一决策的场景。 两种思路回溯 vs 位掩码枚举思路一递归回溯经典思路回溯法的核心模式可以概括为三步选择对当前位的字母先尝试小写再尝试大写递归处理完当前位后递归处理下一位撤销回溯回退时恢复字母状态保证不影响其他分支决策树长这样以 ab 为例 / \ a A / \ / \ ab aB Ab AB每个叶子节点就是一个完整组合遍历整棵二叉树恰好得到 2^n 个结果。这种逐位决策 回退的模式是学习回溯法的最好入口。思路二位掩码枚举airbnb 项目采用airbnb 项目给出的官方解法非常巧妙——用一个整数的二进制位来表示每一种组合整数i从 0 数到 2^n − 1每一个i代表一种组合第j位为 1 → 第 j 个字母用大写为 0 → 用下写例如 ab 中i1二进制 01→ Abi210→ aBi311→ AB这种位运算技巧把递归树压平成了两层循环代码更短、无递归开销是面试中非常加分的写法。 源码解析strComb 是如何工作的参考实现位于 src/main/java/find_case_combinations_of_a_string/FindCaseCombinationsofaString.java核心方法只有十来行public ListString strComb(String text) { ListString 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 个组合i0输出 airbnbi1输出 Airbnbi62输出 aIRBNBi63输出 AIRBNB——与单元测试的断言完全一致见同文件中的 UnitTest.test1。⚙️ 本地运行一键跑通单元测试这个题库基于 Gradle 构建只需两步即可运行本题的测试克隆仓库git clone https://gitcode.com/gh_mirrors/ai/airbnb进入项目目录后运行本题的单测要求 Java ≥ 11.106、Gradle ≥ 5.6.3gradle -Dtest.singleFindCaseCombinationsofaString test测试会验证 4 个关键断言组合总数为 64且首、次、倒数第二、末尾四个组合的值正确帮助你快速确认枚举顺序是否符合二进制递增的规律。 复杂度分析维度复杂度说明时间O(n × 2^n)2^n 种组合每种需 O(n) 构造字符串空间O(n × 2^n)存储全部结果不计递归栈则为 O(n) 临时空间需要清醒认识到2^n 是指数级增长。n 20 时组合数约 100 万n 30 时约 10 亿——这就是为什么题目设定为生成后逐个匹配隐藏串时实际场景通常会配合剪枝如逐位前缀过滤或改用正则匹配(?i)airbnb这类思路来避免全量枚举。 举一反三这道题教会你的 3 件事回溯法的通用框架逐位决策 → 递归深入 → 回溯撤销这套模式可直接迁移到子集生成、全排列、N 皇后等经典题目位运算枚举组合用整数二进制位编码选/不选决策是枚举子集类问题的利器比递归更省栈空间先算数量再动手遇到生成所有组合类题目先问自己总共有多少结果2^nn!能立刻判断算法是否可行完成本题后建议顺藤摸瓜挑战题库中的相邻题目Menu Combination Sum菜单组合求和 和 K Edit DistanceK 编辑距离把组合枚举 匹配过滤的套路彻底练熟。【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考