LeetCode Top 100 高频算法题 Longest Palindromic Substring

╰半橙微兮° 2022-12-26 08:23 174阅读 0赞

LeetCode Top 100高频算法题，即LeetCode上最高频的100道求职面试算法题。小编和实验室同学之前面试找工作，也只刷了剑指offer和这top 100算法题，在实际面试中也遇到了很多LeetCode上的原题。剑指offer算法最优解之前和大家分享了，LeetCode Top 100这100道算法题，每道题小编都刷了很多遍，并且总结了一种最适合面试时手撕算法的最优解法。后续每天和大家分享一道LeetCode top 100高频算法题，以及小编总结的最优解法。

1.  算法题顺序

> LeetCode Top 100 高频算法题系列的LeetCode算法题目就不帮大家翻译了，程序员应该需要能看懂。LeetCode算法题有一个技巧：先看每道题的example，大部分情况看完example就能理解题目意思；如果看完example还有疑惑，可以再回过头来看英文题目。这样也可以节省一点时间~

1.  题目描述

> Given a string s, return the longest palindromic substring in s.

经典的题目，最长回文子串，所谓回文字符串：正反字符串相等  
2. Examples  
**1th example**

> Input: s = “babad”  
> Output: “bab”  
> Note: “aba” is also a valid answer.

2th example

> Input: s = “cbbd”  
> Output: “bb”

3th example

> Input: s = “a”  
> Output: “a”  
> 4th example  
> Input: s = “ac”  
> Output: “a”

1.  Constraints（输入的数据约束）

*  1 <= s.length <= 1000
 *  s consist of only digits and English letters (lower-case and/or upper-case),

**解析**

在LeetCode上本题属于Medium难度。是典型的动态规划类型题目：直接上代码，代码中有详细的注释；代码中提供了2种解法，暴力解法和动态规划

class Solution { 
        public String longestPalindrome(String s){ 
            int length = s.length();
            boolean[][] dp = new boolean[length][length];
            
            int startIndex = 0;
            int maxLength = 0;
            /* 为什么i是从后往前比遍历呢？ 如何判断 i到j是否是回文呢？取决于i+1到j-1的字符串是否是回文，即dp[i]计算的时候，最好是dp[i+1]已经计算完成了 比如：子串:abca,是否是回文取决于子串bc是否是回文（s[0]=s[3]='a'），而子串bc不是回文，即dp[i][j]与dp[i+1][j-1]有关 即dp[i+1]需要在dp[i]之前计算好，所以是从后往遍历 */
            for(int i=length-1;i>=0;i--){ 
                for(int j=i;j<length;j++){ 
                    dp[i][j] = ( s.charAt(i)==s.charAt(j) ) && ( j-i<3 || dp[i+1][j-1]);
                    if(dp[i][j]&&j-i+1>maxLength){ 
                        startIndex = i;
                        maxLength = j-i+1;
                    }
                    
                }
            }
            return s.substring(startIndex,startIndex+maxLength);
            
        }
        
        
        /*public String longestPalindrome(String s) { if(s.length()<=1) return s; int len = s.length(); boolean[][] dp = new boolean[len][len]; int start = 0; int max = -1; //以s.charAt(i)结尾，s.charAt(j)开头的字符串是否是回文 for(int i=0;i<len;i++) for(int j=i;j>=0;j--){ dp[j][i] = (s.charAt(j)==s.charAt(i)) &&( i-j<3 || dp[j+1][i-1] ); if(dp[j][i] && i-j+1>max){ max = i-j+1; start = j; } } return s.substring(start,start+max); }*/
    }

# 其他文章 #

1.  **[免费帮忙下载csdn和百度文库资料福利][csdn]**
2.  **[学习笔记和学习资料汇总：前端 + 后端 + java + 大数据 + python + 100多实战项目 + C++][_ _ _ java _ _ _ python _ 100_ _ C]**
3.  **[我的秋招经历总结：一站式秋招规划][Link 1]**
4.  **[零基础学爬虫][Link 2]**
5.  **[零基础C++学习总结][C]**

欢迎关注个人公众号【**菜鸟名企梦**】，公众号专注：**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术分享：  
公众号**菜鸟名企梦**后台发送“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；

公众号**菜鸟名企梦**后台发送“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，资料很全，你想找的几乎都有

![扫码关注，及时获取更多精彩内容。（博主985、A+学科硕士，今日头条大数据工程师）][985_A]

[csdn]: https://mp.weixin.qq.com/s/7w62D8ftQfUCe3-g5V3egw
[_ _ _ java _ _ _ python _ 100_ _ C]: https://mp.weixin.qq.com/s/sN5ax3Q-IVVfT2cF6BkZAw
[Link 1]: https://mp.weixin.qq.com/s/9bbMiBDZyPUXMY8CJKHFyA
[Link 2]: https://mp.weixin.qq.com/s/Ix0yo_vtPE41QuwW30dHZA
[C]: https://mp.weixin.qq.com/s/VKmOYhbhELXwaelxGy16rw
[985_A]: /images/20221120/7efee399928047d1b5d44577ed5cfe2c.png