LeetCode算法:求出字符串的最大回文子串 及 长度【只利用字符串反转就可】

简介: LeetCode算法:求出字符串的最大回文子串 及 长度【只利用字符串反转就可】

题目描述


  • 给你一个字符串 s,找到 s 中最长的回文子串。
  • 输入:s = “babad”
  • 输出:“bab”
  • 解释:“aba” 同样是符合题意的答案。
    题目思路:
    判断是不是回文串:只需要反转后判断是不是相等
    然后求出所有的子串 并 判断是不是回文,返回最大的即可
/**
 * @author Captain
 * @date 2021/8/19 9:53
 * 给你一个字符串 s,找到 s 中最长的回文子串。
 * 输入:s = "babad"
 * 输出:"bab"
 * 解释:"aba" 同样是符合题意的答案。
 */
public class LongestPalindrome {
    public static String longestPalindrome(String string) {
        // 用来装所有的回文子串
        ArrayList<String> list = new ArrayList<>();
        // 遍历字符串的所有子串
        for (int i = 0; i < string.length(); i++) {
            for (int j = 1; j <= string.length() - i; j++) {
                String sub = string.substring(i,i+j);
                // 如果子串长度大于一 && 是回文串
                if (sub.length()>1 && isPalindorm(sub)){
                    list.add(sub);
                }
            }
        }
        // 定义一个最大回文的长度
        int max = 0;
        for (int i = 0; i < list.size(); i++) {
            max = Math.max(max,list.get(i).length());
        }
        // 取出最大回文子串
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).length() == max){
                return list.get(i);
            }
        }
        return "";
    }
    // 判断是不是回文串
    public static boolean isPalindorm(String s){
        StringBuilder sb = new StringBuilder(s);
        if (sb.reverse().toString().equals(s)){
            return true;
        }
        return false;
    }
    // 主函数测试
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String string = sc.nextLine();
        System.out.println(longestPalindrome(string));
    }
}
目录
打赏
0
0
0
0
15
分享
相关文章
|
4月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
59 0
|
6月前
|
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
4月前
|
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
138 1
两个字符串匹配出最长公共子序列算法
|
4月前
|
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
49 2
|
6月前
|
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
104 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
93 2
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
70 1
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。