算法笔试模拟题精解之“Jerry 的考验”
算法笔试模拟题精解之“Jerry 的考验”
贡献者 | 周剑雄
简介：本题的关键在于理解题意：所谓挑选 n 个字符变成 a 和 b 两个字符串，是
指在原字符串中抽出 n 个字符，这些字符的的顺序保持不变，剩下字符的顺序也保持
不变，由此组成 a 和 b 两个字符串。
题目描述
等级：中等
知识点：搜索、字符串、位运算
查看题目：Jerry 的考验
有一天 Jerry 给 Tom 出了一道题来考验他。Jerry 给了 Tom 一个长度为 2*n
的只包含小写字母的字符串，让 Tom 将这个字符串任意挑选字符，将其分成两个等
长的字符串 a 和 b( 对于一个 si 不能同时被选到 a 和 b 中 )，然后 a 要和 reverse(b)
相同 (a 和反转后的 b 相同 )，问这样的方案数有多少？ Tom 有些为难，所以请你来
帮帮他吧。
输入一个正整数 n，和一个长度为 2*n 的字符串
输出方案数。
示例 1
输入：
输出：
4
解题思路描述
本题的关键在于理解题意：所谓挑选 n 个字符变成 a 和 b 两个字符串，是指在原
字符串中抽出 n 个字符，这些字符的的顺序保持不变，剩下字符的顺序也保持不变，
由此组成 a 和 b 两个字符串。
例如 "abcdef"，挑选第 2、3、5 个字符，则分成 "bce" 和 "adf" 两个串。
接下来是整理的思路解析：整体框架是 dfs，枚举每个字符属于 a 还是属于 b，
搜索过程中需要利用 a 和 b 的对称性做加速处理，否则会超时。
比方说
xcccddcccxdd
从左往右枚举 a 字符串的构成，如果令第一个 x 属于 a，根据对称性，倒数第三
个字符 x 一定是属于 b；如此推导出末尾的 dd 一定属于 a，中间位置的 dd 一定属于
b，而且是 b 的头两个字符；然后左边 ccc 一定 a，右边 ccc 一定是 b，由此得出 1
种方案。令第一个 x 属于 b 也可以用同样的方式得到 1 种方案。
用这个思路直接写代码不太好写，可以通过枚举二进制，固定左半边的选择情
况，然后对于每一个 case，通过 dfs 搜索右半边有多少种合法组合，搜索过程中利
用对称性进行剪枝。
对于字符全部相同 case 如 "aaaaaaaa"，因为过程中无法剪枝，会退化成
2^(2*n)。对于这种 case，答案就是 C(2n,n)，预判一下直接返回即可。
看完之后是不是有了答题思路了呢，快来练练手吧：Jerry 的考验
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”