HJ32 密码截取 | 题解

动态规划算法流程

  • 确定状态:对比的两个字符索引起始和终止索引位置

  • 定义 dp 数组:字符串s的 i 到 j 索引位置的字符组成的子串是否为回文子串

  • 状态转移: 如果左右两字符相等, 同时[j+1...i-1]范围内的字符是回文子串, 则 [j...i] 也是回文子串

  • 状态转移的同时,不断更新对比的子串长度,最终确定最长回文子串的长度
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str = in.nextLine();
            int len = str.length();
            boolean[][] dp = new boolean[len][len];
            int res = 0;
            for (int i = 0; i < len - 1; i++) {
                dp[i][i] = true;
            }
            for (int i = 1; i < len; i++) {
                for (int j = 0; j < i; j++) {
                    if (str.charAt(j) == str.charAt(i) && (j + 1 >= i - 1 || dp[j + 1][i - 1])) {
                        dp[j][i] = true;
                        res = Math.max(res, i - j + 1);
                    }
                }
            }
            System.out.println(res);
        }
    }
}



全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:02
ssob上原来真有BOSS啊
硫蛋蛋:这种也是打工的,只不是是给写字楼房东打工
点赞 评论 收藏
分享
酷酷我灵儿帅:这去不去和线不线下面说实话没啥关系
点赞 评论 收藏
分享
07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务