算法：Jerry的挑战（超时）

港控/mmm° 2023-02-20 15:54 33阅读 0赞

# Jerry的挑战 #

> author: Qiangwei Luo (OVEA)

**问题概述：**  
有一天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

题解：

import org.junit.jupiter.api.Assertions;
    import org.junit.jupiter.api.Test;
    
    public class JerryTest { 
        public long solution(int n, String s) { 
            boolean isSame = false;
            for (int i = 0; i < s.length(); i++) { 
                isSame = true;
                if (s.charAt(0) != s.charAt(i)) { 
                    isSame = false;
                    break;
                }
            }
            // 如果都是同样的字母这种情况
            if (isSame) { 
                return C(n, n * 2);
            } else { 
                // 普通情况
                // 检查字符是否无法构成
                // 用来检查字母
                int[] store = new int[26];
                for (int i = 0; i < s.length(); i++) { 
                    store[s.charAt(i) - 'a']++;
                }
                for (int i = 0; i < store.length; i++) { 
                    if (store[i] % 2 != 0) return 0;
                }
                // 可匹配的情况
                return dfs(s, n, "", 0, "");
            }
        }
    
        /** * 需要的信息 原始字符串，当前加入的位置，当前使用过的字符标记等 * @param s 原始字符串 * @param n 一半单词的数量 * @param left 左半边的词 * @param index 当前指向原始字符串的位置 * @param right 右半边的值 * @return 匹配数量 */
        private long dfs(String s, int n, String left, int index, String right) { 
            int sum = 0;
            // 递归终止条件，left已经到达N了
            if (left.length() == n) { 
                // 补完right的部分
                for (int i = index; i < s.length(); i++) { 
                    right += s.charAt(i);
                }
    // System.out.println(t + " " + left);
                if (left.equals(new StringBuilder(right).reverse().toString())) { 
                    return 1;
                }
                return 0;
            }
            for (int i = index; i < 2 * n; i++) { 
                // right的部分
                String tmpStr = right;
                for (int j = index; j < i; j++) { 
                    tmpStr += s.charAt(j);
                }
                // 统计通过的示例
                sum += dfs(s, n, left + s.charAt(i), i + 1, tmpStr);
            }
            // 返回结果到上一层，直到第一层返回给solution方法
            return sum;
        }
    
        /** * * @param up 上标 * @param down 下标 * @return 排列组合数量 */
        private long C(int up, int down) { 
            int a = 1;
            for (int i = down; i > up; i--) { 
                a *= i;
            }
            int b = 1;
            for (int i = up; i > 0; i--) { 
                b *= i;
            }
            return a / b;
        }
    
        /** * 测试算法结果 */
        @Test
        public void test() { 
    // System.out.println(solution(1, "ab"));
    // System.out.println(solution(2, "abcd"));
            System.out.println(solution(2, "abba"));//4
            Assertions.assertEquals(solution(2, "abba"), 4);
            System.out.println(solution(4, "cabaacba"));//4
            Assertions.assertEquals(solution(4, "cabaacba"), 4);
            System.out.println(solution(15, "dirjbtsgiilnbbjjbbnliigstbjrid")); //73728
            Assertions.assertEquals(solution(15, "dirjbtsgiilnbbjjbbnliigstbjrid"), 73728);
            System.out.println(solution(11, "mippiisssisssiipsspiim")); // 504
            Assertions.assertEquals(solution(11, "mippiisssisssiipsspiim"), 504);
    // System.out.println(solution(2, "aaaa"));
    // System.out.println(CombinationNumberCalculation.nchoosek(4, 2));
    // System.out.println(JerrySolution.solution(2, "aaaa"));
        }
    }

![image-20200628071731167][]

[image-20200628071731167]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pLmxvbGkubmV0LzIwMjAvMDYvMjgvTHlabTNpc2dDZFVFa3ZCLnBuZw?x-oss-process=image/format,png