Leetcode题目总结[5]最长回文子串

题目描述

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

 

示例 1:

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

示例 2:

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

示例 3:

输入:s = "a"
输出:"a"

示例 4:

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

 

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母(大写和/或小写)组成

做法

方法1

暴力做法

从大到小枚举子串并判断该子串是否合法

时间复杂度O(n3)

提交会超时,87/177左右

代码

方法1

 1 /*
 2  * @lc app=leetcode.cn id=5 lang=cpp
 3  *
 4  * [5] 最长回文子串
 5  */
 6 
 7 // @lc code=start
 8 class Solution {
 9 public:
10     string longestPalindrome(string s) {
11         int len1 = s.length();
12         int len2 = len1;
13         //len2--;
14         bool flag = true;
15         string str;
16         if(len1 == 1) return s;
17         //printf("%d %d\n",len1,len2);
18         while(len2)
19         {
20             //printf("%d\n",len2);
21             if(len2 % 2 == 0)
22             {
23                 for(int i = 0; i <= len1 - len2; i++)
24                 {
25                     for(int j = 1; j <= len2 / 2; j++)
26                     {
27                         if(s[i + j - 1] != s[i + len2 - j])
28                         {
29                             flag = false;
30                         }
31                     }
32                     if(flag == true)
33                     {
34                         for(int j = 1; j <= len2; j++)
35                         {
36                             str.push_back(s[i + j - 1]);
37                         }
38                         printf("%d",len2);
39                         return str;
40                     }
41                     flag = true;
42                 }
43             }
44             else
45             {
46                 for(int i = 0; i <= len1 - len2; i++)
47                 {
48                     for(int j = 1; j <= len2 / 2; j++)
49                     {
50                         if(s[i + j - 1] != s[i + len2 - j])
51                         {
52                             flag = false;
53                         }
54                     }
55                     if(flag == true)
56                     {
57                         for(int j = 1; j <= len2; j++)
58                         {
59                             str.push_back(s[i + j - 1]);
60                         }
61                         return str;
62                     }
63                     flag = true;
64                 }
65             }
66             len2--;
67         }
68         return str;
69     }
70 };
71 // @lc code=end

 

Leetcode题目总结[5]最长回文子串

上一篇:自定义泛型方法


下一篇:关于编译和计算机编译的过程