猿创征文｜最长回文子串-力扣

【猿创征文】最长回文子串-力扣

✌字符串快速入门

1. 基本操作对象

• 字符串整体
• 子串 ： 字符串的每个单词。比如“Tom”就是“Tomcat”的子串。通常使用startWith判断开头前缀是否为子串

2. 基本操作

• 连接 ：java中字符串不可变，通过+来进行连接
• 比较 ：.equals方法

4. java中的问题

• 默认字符串不可变，为让字符串可变：使用 toCharArray 将其转换为字符数组
• 经常的连接字符串：最好使用一些数据结构，如 StringBuilder

🍉回文介绍

回文就是字符串的逆转显示和原来的一样，比如"abba"顺序读和逆序读并没有差别

💬最长回文子串问题

给你一个字符串 s，找到 s 中最长的回文子串。比如
输入：s = “babad”
输出：“bab”，其中"aba" 同样是符合题意的答案。
输入：s = “cbbd”
输出：“bb”

🍵最长回文子串解决

通过问题描述发现，回文子串分为奇数回文子串和偶数回文子串，而输入字符串并不能直接确定奇偶，因此需要对奇偶都进行判断。

1. 对于奇数回文，采用中心扩散以中间一个点i为起点判断i的左边第一个和右边第一个是否相等。描述为：
   假设s[i]为中心，判断s[i-1]和s[i+1]是否相等，如果相等，继续判断i的左边第二和右边第二，以此类推
2. 对于偶数回文，采用镜像对称，应该首先判断i和下一个点i+1是否相等，如果相等，也采用中心扩散，只不过是左边的第一个以i为起点，右边的第一个以i+1为起点。

✍️ 算法实现

public String longestPalindrome(String s) {
        int len = s.length();
        int start = 0, end = 0, max_len = 0;
        //定义字符串的长度
        for (int i = 0; i < len; i++) {
        	//i为起点判断i的左边第一个和右边第一个是否相等
            int left = i;
            int right = i;
            //奇数回文"aba",中心回文
            while (left - 1 >= 0 && right + 1 < s.length() && s.charAt(left - 1) == s.charAt(right + 1)) {
                left--;
                right++;
                if (right - left > max_len) {
                    max_len = right - left;
                    start = left;
                    end = right;
                }
            }
            //偶数回文 "abba"
            //先判断和下一个是否相等，然后中心回文
            //左边的第一个以i为起点，右边的第一个以i+1为起点
            left = i;
            right = i + 1;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                if (right - left > max_len) {
                    max_len = right - left;
                    start = left;
                    end = right;
                }
                left--;
                right++;
            }
        }
        return s.substring(start, end + 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

>如果觉得对你有帮助的话:
> 👍 点赞，你的认可是我创作的动力！
> ⭐️ 收藏，你的青睐是我努力的方向！
> 👄 评论，你的意见是我进步的财富！
1
2
3
4