5. 最长回文子串

川长思鸟来 2022-09-08 03:58 141阅读 0赞

[https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/][https_leetcode-cn.com_problems_longest-palindromic-substring_submissions]

难度中等4016

给你一个字符串 `s`，找到 `s` 中最长的回文子串。

**示例 1：**

输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。

**示例 2：**

输入：s = "cbbd"
    输出："bb"

**示例 3：**

输入：s = "a"
    输出："a"

**示例 4：**

输入：s = "ac"
    输出："a"

**提示：**

*  `1 <= s.length <= 1000`
 *  `s` 仅由数字和英文字母（大写和/或小写）组成

通过次数695,741提交次数1,976,409

class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            while(len>0)
            {
                for(int i =0;i+len-1<s.length();i++)
                {
                    // System.out.println(s.substring(i,i+len));
                    if(isHuiwen(s.substring(i,i+len))==true) return s.substring(i,i+len);
                }
                len--;
            }
            return s.charAt(0)+"";
        }
    
        boolean isHuiwen(String s)
        {
            for(int head=0,tail=s.length()-1;head<tail;head++,tail--)
            {
                if(s.charAt(head)!=s.charAt(tail)) return false;
            }
            return true;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16][]

class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            while(len>0)
            {
                for(int i =0;i+len-1<s.length();i++)
                {
                    // System.out.println(s.substring(i,i+len));
                    if(isHuiwen(s,i,i+len-1)==true) return s.substring(i,i+len);
                }
                len--;
            }
            return s.charAt(0)+"";
        }
    
        boolean isHuiwen(String s,int i,int j)
        {
            for(int head=i,tail=j;head<tail;head++,tail--)
            {
                if(s.charAt(head)!=s.charAt(tail)) return false;
            }
            return true;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

时间复杂度：O(n^3)

空间复制度：O(1)

[https_leetcode-cn.com_problems_longest-palindromic-substring_submissions]: https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0cb0bbe95b5c4802abd4ba1f4b87e5ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/fde355b8890e46af924b84819b7228ad.png