106.Jerry的考验 - 图1

题目概述

题目详情(点我)

有一天Jerry给Tom出了一道题来考验他。Jerry给了Tom一个长度为2*n的只包含小写字母的字符串，让Tom将这个字符串任意挑选字符，将其分成两个等长的字符串a和b(对于一个si不能同时被选到a和b中)，然后a要和reverse(b)相同(a和反转后的b相同)，问这样的方案数有多少？Tom有些为难，所以请你来帮帮他吧。

输入:
输入一个正整数n，和一个长度为2*n的字符串

输出:
输出方案数

题解

解题方法

  • dfs

算法知识

  • dfs

    • 时间复杂度: n^2
    • 空间复杂度: n

解题思路

审题

  • int n : 2*n个字符
  • String s: 字符串序列
  • 挑选字符时, 挑选的字符和剩下的字符的顺序不能被改变

题目要求

  • 能够让挑选出来的字符和剩下字符的反转相同的方案数

思路

  • 这个题目得使用到dfs进行处理, 单纯的dfs无法通过这个题目(超时…)
    只有添加判断条件, 才能够顺利通过题目

步骤

  1. 变量定义

    • int cnt[] : 用来存储每个字母字符的出现次数, 容量为26
    • int Ans : 用来存储最终结果, 初始化为0
    • int[] vis : 用来标记对应的下标是否已选取过
    • int[] hav : 下标所对应的字符已选取个数
    • int[] s1 : 用来存储字符串s的字符字符序列

  2. 判断字符串s的个数是否为偶数.

    • 若为奇数, 则直接返回0。因为2*n不可能为奇数

  3. 遍历字符数组s1, 统计每个字符的出现次数

  4. 对每个字符的出现次数进行判断

    • 如果为奇数个, 则直接返回0
    • 如果均为一个字符, 则直接返回组合数C 2n中选n

  5. 使用dfs进行搜索, 并且每次选取的字符串为不合格, 则直接开始下一次筛选

  6. 返回方案数