动态规划学习:最长回文子串-创新互联

最长回文子串

• • 一、最长回文子串
  • 二、代码实现

公司主营业务：网站设计、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联公司推出神木免费做网站回馈大家。一、最长回文子串

• 输入一个字符串,返回它的最长回文子串,如输入ababa,返回aba;输入hello,返回ll

二、代码实现

public class MaxHw {public static String maxhw(String str){int n = str.length();
        if ( n == 0 || n == 1) return str;

        boolean[][] dp = new boolean[n][n];
        //dp[i][j]为true表示字符索引i-j之间为回文子串
        //若s.charAt(i) == s.charAt(j),那么只要dp[i+1][j-1]为true,dp[i][j]也必然为true

        int start = 0;
        int max = 1;
        for (int i = 0; i< n; i++){dp[i][i] = true;
            if (i< n - 1 && str.charAt(i) == str.charAt(i+1)){dp[i][i+1] = true;
                start = i;
                max = 2;
            }
        }

        for (int m = 3; m<= n; m++){for (int i = 0; i + m - 1< n; i++){int j = m + i - 1;
                if (str.charAt(i) == str.charAt(j) && dp[i+1][j-1] == true){dp[i][j] = true;
                    start = i;
                    max = m;
                }
            }
        }
        return str.substring(start,start + max);
    }

    public static void main(String[] args) {String a = "abba";
        System.out.println(maxhw(a));
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享标题：动态规划学习:最长回文子串-创新互联
本文路径：http://bzwzjz.com/article/diejep.html