求字符串中回文子串的数量(Java)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了求字符串中回文子串的数量(Java)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含912字，纯文字阅读大概需要2分钟。

内容图文

/*
*   给定一个字符串，返回这个字符串中有多少个回文子串。
    两个相同的回文子串出现在不同的位置，认为是2个回文子串。
    a、aa、aaa、aba、aabaa、abcba均认为是回文子串。
    输入例子1:
    "aaa"
    
    输出例子1:
    6
    
    例子说明1:
    a、a、a、aa、aa、aaa
*
* */
public class HuiWenExercise {
    public static void main(String[] args) {
        String str = "aabba";
        int count = countH(str);
        System.out.println(count);
    }

    public static int countH(String str) {//动态规划解决
        int sum = 0;
        char[] array = str.toCharArray();
        int size = str.length();
        int[][] arr = new int[size][size];//用二维数组记录回文情况
        for (int i = 0; i < size; i++) {
            arr[i][i] = 1;//长度为1的字串置1
            sum++;
        }

        for (int i = 1; i < size; i++) {
            int j = 0;
            int k = j + i;
            while (k < size) {
                if (array[j] == array[k]) {
                    if (k - j > 1/*j+1<=k-1*/) {
                        arr[j][k] = arr[j + 1][k - 1];//长度大于2的子串调用之前记录的数值
                        sum += arr[j + 1][k - 1];
                    } else {
                        arr[j][k] = 1;//长度小于等于2的子串置1
                        sum++;
                    }

                }
                j++;
                k++;

            }

        }
        return sum;

    }
}

内容总结

以上是互联网集市为您收集整理的求字符串中回文子串的数量(Java)全部内容，希望文章能够帮你解决求字符串中回文子串的数量(Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端