保山网站建设服务,网站制作业务,新闻客户端网站开发,做网站的视频教学题目描述 现有一个字符串s#xff0c;求s的最长回文子串的长度 输入描述 一个字符串s#xff0c;仅由小写字母组成#xff0c;长度不超过100 输出描述 输出一个整数#xff0c;表示最长回文子串的长度 样例
输入
lozjujzve输出
// 最长公共子串为zjujz#xff0c;长度为…题目描述 现有一个字符串s求s的最长回文子串的长度 输入描述 一个字符串s仅由小写字母组成长度不超过100 输出描述 输出一个整数表示最长回文子串的长度 样例
输入
lozjujzve输出
// 最长公共子串为zjujz长度为5
5思路分析
长度由0~n的字符串都可能是回文子串若要使得下标[i,j]指向的字符串是回文子串则必须保证下标[i1,j-1]指向的字符串是回文子串这说明回文子串内部存在一定依赖关系由此可以考虑使用动态规划设置数组dp[n][n]其中n是字符串长度dp[i][j]true代表下标[i,j]指向的字符串arr[]是回文字符串 易知dp[i][i]初始为true因为长度为1的字符串一定是回文字符串进入二重循环第一重定义当前要判断的回文字符串长度第二重确定当前字符串的起始下标i与终止下标j如果arr[i]arr[j]那么说明当前[i,j]有可能是回文子串需要由dp[i1][j-1]是否为true决定其中有一种特殊情况即i1j此时说明当前判断的回文子串长度为2此时首尾字符又相等那么当前一定是回文子串每次确定下一个回文子串后就更新最大长度max 最后输出结果max即可
代码实现
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);char[] arr scanner.next().toCharArray();boolean dp[][] new boolean[arr.length][arr.length];for (int i 0; i arr.length; i) {// 长度为 1 一定是回文串dp[i][i] true;}int max 1;for (int len 2; len arr.length; len) {for (int i 0; i len - 1 arr.length; i) {// i 指向字符串开头元素j 指向字符串最后一个元素int j i len - 1;// 当前首尾元素相同并且原来中间部分也是回文串则当前字符串是回文串// 当首尾元素相同且字符串长度为 2 时当前字符串也是回文串if (arr[i] arr[j] (i 1 j || dp[i 1][j - 1])) {dp[i][j] true;max len;}}}System.out.println(max);}}
