2023华为OD 面试手撕代码真题【切割回文串最小切割次数】

群里小伙伴遇到的题目：算是比较难的题目了。

这个题，解法很多，暴力法、动态规划、Manacher 算法。。。

但是面试给出来，动态规划一定是最完美的答案，说实话你要是牛逼写Manacher 算法，面试官能不能看的懂都是个问题。

1：暴力法，一定要写出来，不一定非要动态规划才行，个人觉的写出暴力法一定可以通过面试。

暴力法的思路也很简单，从1开始遍历，到最多就是切（length-1）次，切成都是单个字符的子串，肯定都是回文串了。中间满足条件直接跳出即可。虽然过不了100%，但是能给出正确解法已经不错了。

class Solution {
    //暴力法，遍历所有的字串
    List<String> ans ;
    boolean[][] judge;
    int cnt;
    int n;
    public int minCut(String s) {
        n = s.length();
        cnt = n-1;
        ans = new ArrayList<>();
        judge = new boolean[n][n]; 
        char[] chars = s.toCharArray();
        for(int i=0;i<n;++i){
            Arrays.fill(judge[i],true);