给定一个字符串数组,如何找到其中最长的回文子串?

简介: 【4月更文挑战第13天】Java动态规划解题:找出字符串数组中最长的回文子串。代码中,`longestPalindrome`函数遍历数组,利用`expandAroundCenter`方法检测以每个字符为中心的回文串并更新最长长度。当遍历完所有字符串后,返回最长回文子串。

在Java中,我们可以使用动态规划的方法来解决这个问题。下面是具体的代码实现:

public class Solution {
   
    public String longestPalindrome(String[] strs) {
   
        if (strs == null || strs.length == 0) {
   
            return "";
        }

        int start = 0, end = 0;
        for (int i = 0; i < strs.length; i++) {
   
            int len1 = expandAroundCenter(strs[i], i, i);
            int len2 = expandAroundCenter(strs[i], i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
   
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return strs[start];
    }

    private int expandAroundCenter(String s, int left, int right) {
   
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
   
            L--;
            R++;
        }
        return R - L - 1;
    }
}

这个函数首先检查输入的字符串数组是否为空,如果为空则直接返回空字符串。然后,它遍历每个字符串,并尝试以该字符串为中心找到最长的回文子串。这是通过调用expandAroundCenter方法来实现的,该方法会向两边扩展,直到找不到相同的字符为止。最后,它返回最长的回文子串。

相关文章
|
6月前
|
存储
【题型总结】寻找满足字符出现奇数次/偶数次的子串个数或者子串最长长度
【题型总结】寻找满足字符出现奇数次/偶数次的子串个数或者子串最长长度
110 0
|
3月前
|
存储 算法 索引
|
6月前
|
机器学习/深度学习 算法 测试技术
【组合数学 容斥原理 逆向思考】2930. 重新排列后包含指定子字符串的字符串数目
【组合数学 容斥原理 逆向思考】2930. 重新排列后包含指定子字符串的字符串数目
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
6月前
【力扣】28. 找出字符串中第一个匹配项的下标
【力扣】28. 找出字符串中第一个匹配项的下标
|
6月前
|
算法 测试技术 C#
【map】【滑动窗口】【字典树】C++算法:最长合法子字符串的长度
【map】【滑动窗口】【字典树】C++算法:最长合法子字符串的长度
|
6月前
|
存储 算法 Java
给定一个二叉树,请你找出其中最长严格递增路径的长度。(提示:使用动态规划)
给定一个二叉树,请你找出其中最长严格递增路径的长度。(提示:使用动态规划)
47 0
|
6月前
|
算法 Java
给定一个字符串数组,如何找到其中最长的回文子串? 要求:编写一个Java函数,输入一个字符串数组,输出其中最长的回文子串。要求时间复杂度为O(n^2)。可以考虑使用动态规划或中心扩展的方法来优化算法。
给定一个字符串数组,如何找到其中最长的回文子串? 要求:编写一个Java函数,输入一个字符串数组,输出其中最长的回文子串。要求时间复杂度为O(n^2)。可以考虑使用动态规划或中心扩展的方法来优化算法。
85 1
|
6月前
|
存储 算法 程序员
【算法训练-字符串 一】【子串问题】最长无重复子串、最长回文子串、最长公共前缀
【算法训练-字符串 一】【子串问题】最长无重复子串、最长回文子串、最长公共前缀
67 0
剑指offer 49. 最长不含重复字符的子字符串
剑指offer 49. 最长不含重复字符的子字符串
67 0