讨论/《腾讯》 - 最长回文子串/
《腾讯》 - 最长回文子串
共 2 个回复

1,中心扩散法

中心扩散法也很好理解,我们遍历字符串的每一个字符,然后以当前字符为中心往两边扩散,查找最长的回文子串,下面随便举个例子,看一下视频演示


视频中我们是以每一个字符为中心,往两边扩散,来求最长的回文子串。但忽略了一个问题,回文串的长度不一定都是奇数,也可能是偶数,比如字符串"abba",如果使用上面的方式判断肯定是不对的。


我们来思考这样一个问题,如果是单个字符,我们可以认为他是回文子串,如果是多个字符,并且他们都是相同的,那么他们也是回文串


所以对于上面的问题,我们以当前字符为中心往两边扩散的时候,先要判断和他挨着的有没有相同的字符,如果有,则直接跳过,来看下代码

String longestPalindrome(String s) {
    //边界条件判断
    if (s.length() < 2)
        return s;
    //start表示最长回文串开始的位置,
    //maxLen表示最长回文串的长度
    int start = 0, maxLen = 0;
    int length = s.length();
    for (int i = 0; i < length; ) {
        //如果剩余子串长度小于目前查找到的最长回文子串的长度,直接终止循环
        // (因为即使他是回文子串,也不是最长的,所以直接终止循环,不再判断)
        if (length - i <= maxLen / 2)
            break;
        int left = i, right = i;
        while (right < length - 1 && s.charAt(right + 1) == s.charAt(right))
            ++right; //过滤掉重复的
        //下次在判断的时候从重复的下一个字符开始判断
        i = right + 1;
        //然后往两边判断,找出回文子串的长度
        while (right < length - 1 && left > 0 && s.charAt(right + 1) == s.charAt(left - 1)) {
            ++right;
            --left;
        }
        //保留最长的
        if (right - left + 1 > maxLen) {
            start = left;
            maxLen = right - left + 1;
        }
    }
    //截取回文子串
    return s.substring(start, start + maxLen);
}

再来看一下运行结果
image.png


2,暴力求解

暴力求解是最容易想到的,要截取字符串的所有子串,然后再判断这些子串中哪些是回文的,最后返回回文子串中最长的即可

这里我们可以使用两个变量,一个记录最长回文子串开始的位置,一个记录最长回文子串的长度,最后再截取。代码如下

public String longestPalindrome(String s) {
    if (s.length() < 2)
        return s;
    int start = 0;
    int maxLen = 0;
    for (int i = 0; i < s.length() - 1; i++) {
        for (int j = i; j < s.length(); j++) {
            //截取所有子串,然后在逐个判断是否是回文的
            if (isPalindrome(s, i, j)) {
                if (maxLen < j - i + 1) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }
    }
    return s.substring(start, start + maxLen);
}

//判断是否是回文串
private boolean isPalindrome(String s, int start, int end) {
    while (start < end) {
        if (s.charAt(start++) != s.charAt(end--))
            return false;
    }
    return true;
}

暴力求解毕竟效率很差,我们看下运行结果,超时了

image.png

实际上面代码其实还可以优化一下,在截取的时候,如果截取的长度小于等于目前查找到的最长回文子串,我们可以直接跳过,不需要再判断了,因为即使他是回文子串,也不可能是最长的。

public String longestPalindrome(String s) {
    if (s.length() < 2)
        return s;
    int start = 0;
    int maxLen = 0;
    for (int i = 0; i < s.length() - 1; i++) {
        for (int j = i; j < s.length(); j++) {
            //截取所有子串,如果截取的子串小于等于之前
            //遍历过的最大回文串,直接跳过。因为截取
            //的子串即使是回文串也不可能是最大的,所以
            //不需要判断
            if (j - i < maxLen)
                continue;
            if (isPalindrome(s, i, j)) {
                if (maxLen < j - i + 1) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }
    }
    return s.substring(start, start + maxLen);
}

//判断是否是回文串
private boolean isPalindrome(String s, int start, int end) {
    while (start < end) {
        if (s.charAt(start++) != s.charAt(end--))
            return false;
    }
    return true;
}

看一下运行结果,虽然没有超时,但效率很差
image.png


3,动态规划

定义二维数组dp[length][length],如果dp[left][right]为true,则表示字符串从left到right是回文子串,如果dp[left][right]为false,则表示字符串从leftright不是回文子串。


如果dp[left+1][right-1]为true,我们判断s.charAt(left)s.charAt(right)是否相等,如果相等,那么dp[left][right]肯定也是回文子串,否则dp[left][right]一定不是回文子串。


所以我们可以找出递推公式

 dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1]


有了递推公式,还要确定边界条件:

如果s.charAt(left)!=s.charAt(right),那么字符串从left到right是不可能构成子串的,直接跳过即可。


如果s.charAt(left)==s.charAt(right),字符串从left到right能不能构成回文子串还需要进一步判断

  • 如果left==right,也就是说只有一个字符,我们认为他是回文子串。即dp[left][right]=true(left==right)
  • 如果right-left<=2,类似于"aa",或者"aba",我们认为他是回文子串。即dp[left][right]=true(right-left<=2)
  • 如果right-left>2,我们只需要判断dp[left+1][right-1]是否是回文子串,才能确定dp[left][right]是否为true还是false。即dp[left][right]=dp[left+1][right-1]

有了递推公式和边界条件,代码就很容易写了,来看下

public static String longestPalindrome(String s) {
    //边界条件判断
    if (s.length() < 2)
        return s;
    //start表示最长回文串开始的位置,
    //maxLen表示最长回文串的长度
    int start = 0, maxLen = 1;
    int length = s.length();
    boolean[][] dp = new boolean[length][length];
    for (int right = 1; right < length; right++) {
        for (int left = 0; left < right; left++) {
            //如果两种字符不相同,肯定不能构成回文子串
            if (s.charAt(left) != s.charAt(right))
                continue;

            //下面是s.charAt(left)和s.charAt(right)两个
            //字符相同情况下的判断
            //如果只有一个字符,肯定是回文子串
            if (right == left) {
                dp[left][right] = true;
            } else if (right - left <= 2) {
                //类似于"aa"和"aba",也是回文子串
                dp[left][right] = true;
            } else {
                //类似于"a******a",要判断他是否是回文子串,只需要
                //判断"******"是否是回文子串即可
                dp[left][right] = dp[left + 1][right - 1];
            }
            //如果字符串从left到right是回文子串,只需要保存最长的即可
            if (dp[left][right] && right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
        }
    }
    //截取最长的回文子串
    return s.substring(start, start + maxLen);
}

来看下运行结果

image.png


我把部分算法题整理成了PDF文档,截止目前总共有1000多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

1
var longestPalindrome = function(s) {
if (!s || s.length < 2) {
    return s
}

const len = s.length
let maxLen =  0
let start, end

for (let  i = 0; i < len; i ++) {
    let left = right = i;

    while ( right + 1 < len && s[i] == s[right + 1]) {
        right ++
    }


    while (left > 0 && right < len - 1 && s[left -  1] === s[right + 1]) {
        left --
        right ++
    }
    
    if (right - left + 1 > maxLen) {
        start = left
        end = right
        maxLen = right - left + 1

    }
}
return s.slice(start, end + 1)

};