笔试算法模拟题精解之“Jerry的考验”-阿里云开发者社区

开发者社区> 算法编程> 正文

笔试算法模拟题精解之“Jerry的考验”

简介: 本题的关键在于理解题意:所谓挑选n个字符变成a和b两个字符串,是指在原字符串中抽出n个字符,这些字符的的顺序保持不变,剩下字符的顺序也保持不变,由此组成a和b两个字符串。

【在线编程产品介绍】

阿里云开发者社区在线编程:

免费刷题大神器,助你拿到好offer

周赛月赛不停歇,做题还能领奖品

大赛笔试全真题,常做常新有惊喜

点击链接开始产品体验:https://developer.aliyun.com/coding

本文为大家介绍的是“106.Jerry的考验”的解法探究。先来看一下题目内容:

题目详情

等级:中等
知识点:搜索、字符串、位运算
查看题目:Jerry的考验

有一天Jerry给Tom出了一道题来考验他。Jerry给了Tom一个长度为2*n的只包含小写字母的字符串,让Tom将这个字符串任意挑选字符,将其分成两个等长的字符串a和b(对于一个si不能同时被选到a和b中),然后a要和reverse(b)相同(a和反转后的b相同),问这样的方案数有多少?Tom有些为难,所以请你来帮帮他吧。
输入一个正整数n,和一个长度为2*n的字符串
输出方案数。
示例1
输入:
2
"abba"
输出:
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) ,预判一下直接返回即可。

看完之后是不是有了答题思路了呢,快来练练手吧:106.Jerry的考验

在线编程周赛、月赛火热进行中,更有限时答题活动,社区定制卫衣、双肩背包等你来拿~每周都有好礼相送~点击了解周赛详情:在线编程3月份比赛正式开启!机械键盘等你拿!

b462f1d86b44481ca24c0ad63fe55948.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接