华为OD机试真题 Java 实现【最长回文子串】【牛客练习题】

一、题目描述

给定一个仅包含小写字母的字符串，求它的最长回文子串的长度。
所谓回文串，指左右对称的字符串。
所谓子串，指一个字符串删掉其部分前缀和后缀（也可以不删）的字符串

数据范围：字符串长度1≤s≤350

进阶：时间复杂度：O(n)\O(n) ，空间复杂度：O(n)\O(n)

二、输入描述

输入一个仅包含小写字母的字符串。

三、输出描述

返回最长回文子串的长度。

四、解题思路

1. 输入一个仅包含小写字母的字符串；
2. 定义一个max，用于记录最长回文子串的长度；
3. 使用双重for循环遍历字符串的所有可能子串，从左到右取子串；
4. 对于每个子串，判断其是否是回文串；
5. 如果是回文串，则更新max的值为当前子串长度和max中的较大值；
6. 结束循环，max的值即为最长回文子串的长度；

五、Java算法源码

public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    // 输入一个仅包含小写字母的字符串
    String str = sc.nextLine();
    // 最长回文子串的长度
    int max = 0;

	// 使用双重for循环遍历字符串的所有可能子串，从左到右取子串
    for (int i = 0; i < str.length(); i++) {
        for (int j = str.length(); j > i; j--) {
        	// 对于每个子串，判断其是否是回文串
            if (isPalindrome(str.substring(i, j))) {
            	// 如果是回文串，则更新max的值为当前子串长度和max中的较大值
                max = Math.max(max, j - i);
            }
        }
    }
    System.out.print(max);
}

// 判断是否是回文串
private static boolean isPalindrome(String s) {
    return s.equals(new StringBuilder(s).reverse().toString());
}

六、效果展示

🏆下一篇：华为OD机试真题 Java 实现【基站维修工程师】【2023Q1 200分】，附详细解题思路

🏆本文收录于，华为OD机试（JAVA）（2022&2023）

本专栏包含了最新最全的2023年华为OD机试真题，有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新，每天在线答疑。