遇到一个位运算问题，求解答
有一天Jerry给Tom出了一道题来考验他。Jerry给了Tom一个长度为2n的只包含小写字母的字符串，让 Tom 将这个字符串任意挑选字符，将其分成两个等长的字符串 a 和 b( 对于一个 si 不能同时被选到 a 和 b 中 )，然后 a 要和 reverse(b)相同 (a 和反转后的 b 相同 )，问这样的方案数有多少？ Tom 有些为难，所以请你来帮帮他吧。输入一个正整数 n，和一个长度为 2n 的字符串输出方案数。
写回答
-
本题的关键在于理解题意：所谓挑选 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)，预判一下直接返回即可。 因此输入：2 "abba" 输出：4
2021-12-23 18:58:11赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
